2141

完全没有想到任何解法，直接看了题解

纯sort

设最后答案为x, 总电脑量n, len(batteries) = m

因为sum(batteries)/n <= max(batteries)，所以我们可以拿出来一个给电脑用x的电量。我们可以依次类推，直到第k个电池，也就是说sum(batteries)/(n - k) >= max(batteries[:n - k]), 到这里我们发现没有办法再让电脑用一个电池到x，剩下的电脑分剩下的电池就是我们的答案。

1. 为什么这个k的电池都会比x大？
   • 可以用反证法, 设k个电池种有至少一个没有x大。设这个电池是k_x, 我们可以得到sum(batteries)/(n - k_x) <= batteries[m-1-k_x] < x, 发现剩下的平均电量比x还小，也就是说剩下的电池无法支持剩下的电脑同时运作。
   • 补充: 是否有可能前面几个电池加进去能刚好补充？ 答: 不能，因为这里答案x前面几个电脑也要跑x没办法跑到一半把电池给别人用
2. 为什么剩下的电脑分剩下的电池是答案？
   • 因为sum(batteries)/(n - k) >= max(batteries[:n - k]) ，也就是说接下来剩下的电池都比average小，但我们有average意味着有多余的电池可以让我们可以塞电池换电池，因为一个电脑用多组电池，所以这时我们可以彻底的拆分调动顺序使条件满足

Binary Search

参考0x3f

下面证明当 $n\cdot x\le sum$ 成立时，必然可以让 $n$ 台电脑同时运行 $x$ 分钟。

1. 对于电量不小于 $x$ 的电池，我们可以让其给一台电脑供电 $x$ 分钟。由于一个电池不能同时给多台电脑供电，因此该电池若给一台电脑供电 $x$ 分钟，那它就不能用于其他电脑了（因为电脑运行时间就是 $x$ 分钟）。我们可以将所有电量不小于 $x$ 的电池各给一台电脑供电。
2. 对于其余的电池，设其电量和为 $sum'$，剩余 $n'$ 台电脑未被供电。我们可以随意选择剩下的电池，供给剩余的第一台电脑（用完一个电池就换下一个电池），多余的电池电量与剩下的电池一起供给剩余的第二台电脑，依此类推。注意由于这些电池的电量均小于 $x$，按照这种做法是不会出现同一个电池在同一时间供给多台电脑的（如果某个电池供给了两台电脑，可以将这个电池的供电时间划分到第一台电脑的末尾和第二台电脑的开头）。
3. 由于 $sum'=sum−(n−n′)\cdot x$ 结合 $n⋅x\le sum$ 可以得到 $n'⋅x\le sum'$，按照上述供电方案（用完一个电池就换下一个电池），这台电脑可以运行至少 $x$ 分钟。充分性得证。
4. 如果我们可以让 $n$ 台电脑同时运行 $x$ 分钟，那么必然也可以同时运行低于 $x$ 分钟，因此答案满足单调性，可以二分答案，通过判断 $n\cdot x\le sum$ 来求解。 作者：灵茶山艾府 链接：https://leetcode.cn/problems/maximum-running-time-of-n-computers/solutions/1214440/liang-chong-jie-fa-er-fen-da-an-pai-xu-t-grd8/