贪心的猴子
题目
描述
在动物园中，一群猴子排队领香蕉，每只猴子都有一个最少的香蕉需求量。
猴子很贪心，每只猴子拿香蕉时可能会拿多于自己最少需求量的香蕉。
每只猴子就算多拿香蕉，拿的香蕉数目也不会超过自身需求量的两倍，同时也不会超过剩余香蕉数量的一半。
最后一只猴子是例外，他可以把所有剩余的香蕉都拿走。
如果你是动物园饲养员，负责为猴子准备香蕉，在已知猴子总数和每只猴子的最少香蕉需求量时，
至少准备多少香蕉，才能保证每只猴子拿到的香蕉都能满足自己的需求。
输入
第一行：整数\(n\)，表示猴子的总数，\(0\le n\le100\)
第二行：\(n\)个整数，第\(i\)个整数为\(e_i\)，表示第\(i\)只猴子的最少香蕉需求量，\(1\le e_i \le 1000\)
输出
输出一整数，表示最少需要准备的香蕉的数量。
样例
输入样例1
1 | |
输出样例1
1 | |
其他样例见 problem/week-1-1
解析
解决问题的方法不唯一，我这里展示的一定不是最优解法。
符号说明
| 符号 | 备注 |
|---|---|
| \(i\) | 猴子序号，从\(0\)到\(n-1\) |
| \(e_i\) | 第\(i\)只猴子香蕉的最小需求量 |
| \(E_i\) | 第\(i\)只猴子实际拿的香蕉数量 |
| \(R_i\) | 该第\(i\)只猴子拿香蕉时，所剩余的香蕉数量 |
关系表述
用以上定义的符号去表述问题中描述的关系
关系1
猴子拿香蕉时，香蕉剩余量必须大于等于猴子最小需求量
\[ R_i \ge e_i \]
关系2
对于\(i \in [0, n -1)\)，每只猴子实际拿的香蕉数量满足
\[ e_i \le E_i \le \min \{2 e_i, \lfloor R_i / 2 \rfloor\} \]
关系3
对于\(i = n-1\)，即最后一只猴子
\[ E_i = R_i \]
关系4
对于\(i \in [0, n - 1)\) 满足 \[ R_i = \sum_{k = i}^{n - 1} E_k \]
关系解析
解析1
对于\(i \in [0, n - 1)\)，每只猴子足够贪婪，永远会选择当前最优选择
由关系1和关系2可知 \[ E_i = \min\{2e_i, \lfloor R_i / 2 \rfloor \} \ge e_i \] 引入关系4，将\(R_i\)替换为\(E_i\)的表达式 \[ E_i = \min\{2e_i, \lfloor \sum_{k = i}^{n - 1} E_k / 2 \rfloor \} \ge e_i \]
解析2
由关系1和关系3可知 \[ E_{n - 1} = R_{n - 1} \ge e_{n - 1} \]
目标分析
- 当\(i = n - 1\)时，\(E_i \ge e_i\)
- 当\(i \in [0, n - 1)\)时，\(E_i = \min\{2e_i, \lfloor \sum_{k = i}^{n - 1} E_k / 2 \rfloor \}\)
观察可知，\(E_i\)由\(E_{n - 1}\)和\(e_i\)决定，而\(e_i\)已知，故将\(E_{n-1}\)看做未知量进行推导。
对于\(i\in[0, n-1)\)，当\(\lfloor \sum_{k = i}^{n - 1} E_k / 2 \rfloor \le 2e_i\)时
- 【偶数假设】如果\(\sum_{k = i}^{n - 1}E_k\)为偶数，有\(2E_i = E_i + \sum_{k = i +1}^{n - 1}E_k\) 即 \(E_i = \sum_{k = i + 1}^{n - 1} E_k\)
- 【奇数假设】如果\(\sum_{k = i}^{n - 1}E_k\)为奇数，有\(2E_i = E_i + \sum_{k = i +1}^{n - 1}E_k - 1\) 即 \(E_i = \sum_{k = i + 1}^{n - 1} E_k - 1\)
即\(E_i\)可以由\(E_k\)表出，\(k \in [i + 1, n - 1]\)
观察奇数偶数假设
- 当\(E_i = \sum_{k = i + 1}^{n - 1} E_k\)时，\(\sum_{k = i}^{n - 1}E_k = E_i + \sum_{k = i + 1}^{n-1}E_k = 2 \sum_{k = i + 1}^{n-1}E_k\)，故偶数假设成立
- 当\(E_i = \sum_{k = i + 1}^{n - 1} E_k - 1\)时，\(\sum_{k = i}^{n - 1}E_k = E_i + \sum_{k = i + 1}^{n-1}E_k -1= 2 \sum_{k = i + 1}^{n-1}E_k -1\)，故奇数假设成立
局部最优
对于\(i \in [0, n -1)\)，将\(E_{n-1}\)和\(i\)看做自变量，\(E_i\)看做因变量
可得函数关系： \[ E_i = f(E_{n-1}, i) = \min\{2e_i, \sum_{k = i + 1}^{n-1}E_k - 1, \sum_{k = i + 1}^{n-1}E_k\} \ge e_i \] 如果控制\(E_{n-1}\)的量，使得每只猴子实际能拿的最多的香蕉的数量最少，则认为整体香蕉的消耗量最少，即局部最优等于全局最优。
即对于给定\(i\)，求解\(E_{n-1}\) \[ {\operatorname {arg\,min} }\,f(E_{n-1}, i):=\{E_{n-1}\mid E_{n-1} \ge e_{n-1}:f(E_{n-1})\geq e_i\} \]