https://leetcode.com/problems/maximum-running-time-of-n-computers/
好题目，题干问题本身比较有使用价值，就是一个统筹策划的问题。
题目的解法也用到了归约的思想，设计的还是非常巧妙的。

个人解答

  1. class Solution:
  2.     def maxRunTime(self, n: int, bs: List[int]) -> int:
  3.         s = sum(bs)
  4.         bs.sort()
  5.         for x in bs[::-1]:
  6.             if x > s // n:
  7.                 n -= 1
  8.                 s -= x
  9.         return s // n

思路分析

参考：https://leetcode.com/problems/maximum-running-time-of-n-computers/discuss/1692939/JavaC%2B%2BPython-Sort-Solution-with-Explanation-O(mlogm))

这道题是周赛的最后一题，并没有做出来，看了解答，简直妙啊妙啊。

一开始的思路比较直接：每次都用剩余电量最多的n个，这样就保证不浪费。
但是维护动态变化的最多的n个不是那么容易。
首先想到heap实现，每次pop出n个，-1之后再push回去。
后来想到可以优化，每次不-1，而是直接减到比剩余元素小1。这一定程度可以提高效率，但还是超时了。

所以根据题目中的10^5的数据量，这样的模拟操作是无法接受的，需要换个思路。

理想状况下，电池都能够用完，可以坚持s // n时间。但如果有n-1或更少的电池太多了，最后只剩下n-1个电池，就没办法继续利用了。
而且，电量超过s // n电池的肯定用不完，那么说明一直用它给一个计算机供电，并不会产生浪费。
于是，问题似乎可以转化为，剩下的电池对于剩下的计算机能够坚持多久。这里还需要论证一下，最多的这个会不会浪费。
其实并不会，因为一个电池不能掰成两截用，这个电池一直给一个计算机供着电。只要其它的能把剩下的计算机供起来，它也能陪得起；反之，如果其它的完不成，它也抽不出身。
所以这个归约是成立的。
直到最后，n == 1或者剩下的正好平均的时候，剩下的全填上就好了，便是剩下的总量除以当时的n: s // n

妙啊妙啊！