LC 2141. 同时运行 N 台电脑的最长时间

https://leetcode-cn.com/problems/maximum-running-time-of-n-computers/

大概猜想到是二分查找，但总是觉得有某些情况没有考虑到：一个电池在中途挪去到另外一个地方充电，这个问题怎么解决呢？

其实这个放置如果画出来的话，可能就容易理解了。比如这个链接里面给出的图片

假设我们二分查找是进行 `check(k)`
虽然红色进行了迁移，但是如果把红色挪回来的话，还是可以看红色最多使用 k 个
而对于少于k个的电池，在任何时候任何地方都可以被使用
所以最终可用的总电量是 `sum((min(x, k) for x in batteries))`
然后就是看这些总电量，是否可以支撑n个电脑。

这样的话代码就很好写了。

class Solution:
    def maxRunTime(self, n: int, batteries: List[int]) -> int:
        batteries.sort(reverse = True)

        def check(k):
            tt = 0
            for x in batteries:
                tt += min(x, k)
            return tt >= n * k

        s, e = 0, sum(batteries)
        while s <= e:
            m = (s + e) // 2
            if check(m):
                s = m + 1
            else:
                e = m - 1
        return e

然后第一名还有个更好的方案，其实也可以通过上面这个图片推导过来：

如果红色电池特别长超过平均值，那么其实红色电池不会瓶颈，所以我们可以丢弃它。
当剩余的电池电量刚好都差不多的时候，并且最长的电池没有超过平均值时，那么此时的平均值就是极限。

class Solution:
    def maxRunTime(self, n: int, batteries: List[int]) -> int:
        batteries.sort(reverse = True)

        tt = sum(batteries)
        avg = 0
        for x in batteries:
            avg = tt // n
            if x > avg:
                n -= 1
                tt -= x
            else:
                break

        return avg

一旦画出上面这幅图，从另外一个视角来分析问题，有时候问题就会迎刃而解。而能否画出这幅图，则要看是否有着深入的insight, 这就是水平了。