贪心的猴子

题目

来源 problem/week-1-1

描述

在动物园中，一群猴子排队领香蕉，每只猴子都有一个最少的香蕉需求量。

猴子很贪心，每只猴子拿香蕉时可能会拿多于自己最少需求量的香蕉。

每只猴子就算多拿香蕉，拿的香蕉数目也不会超过自身需求量的两倍，同时也不会超过剩余香蕉数量的一半。

最后一只猴子是例外，他可以把所有剩余的香蕉都拿走。

如果你是动物园饲养员，负责为猴子准备香蕉，在已知猴子总数和每只猴子的最少香蕉需求量时，

至少准备多少香蕉，才能保证每只猴子拿到的香蕉都能满足自己的需求。

输入

第一行：整数n，表示猴子的总数，0≤n≤100

第二行：n个整数，第i​​个整数为ei，表示第i只猴子的最少香蕉需求量，1≤ei≤1000

输出

输出一整数，表示最少需要准备的香蕉的数量。

样例

输入样例1

3
1 4 3
BASIC

输出样例1

10
TXT

其他样例见 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=n−1∑k=iEk

关系解析

解析1

对于i∈[0,n−1)​，每只猴子足够贪婪，永远会选择当前最优选择

由关系1和关系2可知 Ei=min{2ei,⌊Ri/2⌋}≥ei

引入关系4，将Ri替换为Ei的表达式 Ei=min{2ei,⌊n−1∑k=iEk/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,⌊∑n−1k=iEk/2⌋}

观察可知，Ei​由En−1​和ei​决定，而ei​已知，故将En−1​看做未知量进行推导。

---

对于i∈[0,n−1)​​，当⌊∑n−1k=iEk/2⌋≤2ei​​​​时

• 【偶数假设】如果∑n−1k=iEk​为偶数，有2Ei=Ei+∑n−1k=i+1Ek​ 即 Ei=∑n−1k=i+1Ek​
• 【奇数假设】如果∑n−1k=iEk​​​为奇数，有2Ei=Ei+∑n−1k=i+1Ek−1​​​ 即 Ei=∑n−1k=i+1Ek−1​

即Ei可以由Ek表出，k∈[i+1,n−1]

观察奇数偶数假设

• 当Ei=∑n−1k=i+1Ek时，∑n−1k=iEk=Ei+∑n−1k=i+1Ek=2∑n−1k=i+1Ek，故偶数假设成立
• 当Ei=∑n−1k=i+1Ek−1​​时，∑n−1k=iEk=Ei+∑n−1k=i+1Ek−1=2∑n−1k=i+1Ek−1​​，故奇数假设成立

局部最优

对于i∈[0,n−1)，将En−1和i看做自变量，Ei看做因变量

可得函数关系： Ei=f(En−1,i)=min{2ei,n−1∑k=i+1Ek−1,n−1∑k=i+1Ek}≥ei

如果控制En−1​​的量，使得每只猴子实际能拿的最多的香蕉的数量最少，则认为整体香蕉的消耗量最少，即局部最优等于全局最优。

即对于给定i​，求解En−1 argminf(En−1,i):={En−1∣En−1≥en−1:f(En−1)≥ei}