leetcode：2141. 同时运行 N 台电脑的最长时间【最值考虑二分】

分析

n <= batteries.length 不会出现电脑更多的情况
这里要有贪心思维
我们知道如果在固定n台电脑的情况下，我们可以判断运行x分钟是否可行
具体的手法就是每个电池取min(x, battery[i])这个就是它的有效使用时常
全部叠加起来看看和n * x的大小即可
一个是x分钟最多提供的电量 一个是x分钟需要提供的电量
然后check返回BOOl，最后用一点二分的技巧解决即可

ac code

class Solution:
    def maxRunTime(self, n: int, batteries: List[int]) -> int:
        # 最值问题考虑二分
        # 给定分钟数，可以得到最多能运行的电脑书
        # 分钟数越长，同时运行的电脑越少
        m = len(batteries)
        # 直接看看能不能运行mins分钟
        def check(mins):
            valid_mins = [min(mins, batteries[i]) for i in range(m)]
            return sum(valid_mins) >= n * mins


        l, r = 1, 10 ** 14 # 1 should be starter
        while l + 1 < r:
            mid = (l + r) // 2
            if check(mid):
                l = mid
            else:
                r = mid - 1
        
        for ans in range(r, l - 1, -1):
            if check(ans):
                return ans

总结

注意细节，注意模拟，注意思维简单化
最值问题考虑二分