在动物园中，一群猴子排队领香蕉，每只猴子都有一个最少的香蕉需求量。
猴子很贪心，每只猴子拿香蕉时可能会拿多于自己最少需求量的香蕉。
每只猴子就算多拿香蕉，拿的香蕉数目也不会超过自身需求量的两倍，同时也不会超过剩余香蕉数量的一半。
最后一只猴子是例外，他可以把所有剩余的香蕉都拿走。
如果你是动物园饲养员，负责为猴子准备香蕉，在已知猴子总数和每只猴子的最少香蕉需求量时，
至少准备多少香蕉，才能保证每只猴子拿到的香蕉都能满足自己的需求。
第一行：整数\(n\)，表示猴子的总数，\(0\le n\le100\)
第二行：\(n\)个整数，第\(i\)个整数为\(e_i\)，表示第\(i\)只猴子的最少香蕉需求量，\(1\le e_i \le 1000\)
输出一整数，表示最少需要准备的香蕉的数量。
1 | |
1 | |
其他样例见 problem/week-1-1
解决问题的方法不唯一，我这里展示的一定不是最优解法。
| 符号 | 备注 |
|---|---|
| \(i\) | 猴子序号，从\(0\)到\(n-1\) |
| \(e_i\) | 第\(i\)只猴子香蕉的最小需求量 |
| \(E_i\) | 第\(i\)只猴子实际拿的香蕉数量 |
| \(R_i\) | 该第\(i\)只猴子拿香蕉时，所剩余的香蕉数量 |
用以上定义的符号去表述问题中描述的关系
猴子拿香蕉时，香蕉剩余量必须大于等于猴子最小需求量
\[R_i \ge e_i\]
对于\(i \in [0, n-1)\)，每只猴子实际拿的香蕉数量满足
\[e_i \le E_i \le \min \{2 e_i, \lfloor R_i / 2 \rfloor\}\]
对于\(i = n-1\)，即最后一只猴子
\[E_i = R_i\]
对于\(i \in [0, n - 1)\) 满足 \[R_i = \sum_{k = i}^{n - 1} E_k\]
对于\(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 \} \gee_i\]
由关系1和关系3可知 \[E_{n - 1} = R_{n - 1} \ge e_{n - 1}\]
观察可知，\(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 \le2e_i\)时
即\(E_i\)可以由\(E_k\)表出，\(k\in [i + 1, n - 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} \gee_{n-1}:f(E_{n-1})\geq e_i\}\]