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