算法-贪婪的猴子

本文最后更新于：1 分钟前

来源 problem/week-1-1

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

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

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

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

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

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

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

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

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

输入样例1

3
1 4 3

输出样例1

10

其他样例见 problem/week-1-1

符号 备注

猴子序号，从到 ​ 第只猴子香蕉的最小需求量

第只猴子实际拿的香蕉数量

该第只猴子拿香蕉时，所剩余的香蕉数量

用以上定义的符号去表述问题中描述的关系

猴子拿香蕉时，香蕉剩余量必须大于等于猴子最小需求量

对于i∈[0,n−1)i∈[0,n−1)​​，每只猴子实际拿的香蕉数量满足

对于i=n−1i=n−1，即最后一只猴子

对于i∈[0,n−1)i∈[0,n−1)​ 满足

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

由关系1和关系2可知

由关系1和关系3可知

综合解析1与解析2可得

• 当i=n−1i=n−1时，Ei≥eiEi≥ei
• 当i∈[0,n−1)i∈[0,n−1)时，Ei=min{2ei,⌊∑n−1k=iEk/2⌋}Ei=min{2ei,⌊∑k=in−1Ek/2⌋}

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

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

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

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

观察奇数偶数假设

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

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

可得函数关系：

即对于给定ii​，求解En−1En−1