贪心的猴子

题目

来源 problem/week-1-1

描述

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

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

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

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

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

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

输入

第一行:整数\(n\),表示猴子的总数,\(0\le n\le100\)

第二行:\(n\)个整数,第\(i\)​​个整数为\(e_i\),表示第\(i\)只猴子的最少香蕉需求量,\(1\le e_i \le 1000\)

输出

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

样例

输入样例1

1
2
3
1 4 3

输出样例1

1
10

其他样例见 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} \]

目标分析

综合解析1解析2可得

  • \(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\} \]


贪心的猴子
https://blog.scubot.com/article/9102/
作者
贺翔/CarOL
发布于
2022年1月21日
许可协议