[数据结构与算法]leetcode：1760. 袋子里最少数目的球【最值的最值 + 二分板子】

分析

最值的最值可以考虑二分
找到单调性！！！
怎么找？
我们分析一下
如果单个袋子球得最大值越大，是不是操作得次数越小？
反之，最大值越小，是不是操作得越大；
我们构建一个函数可以通过给定单个袋子得最大值求出其最小操作次数
然后我们要求最小得最大值
所以我们判断cal_ops(mid)
如果这个值小于等于maxOps，说明最大值还可以更小，所以r 取 mid，是可以成功得
反之，如果大于maxOps，操作数过多，说明要增大最大值，此时mid已经凉凉
所以要l = mid + 1
最后返回最小值所以返回l

ac code

class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        # 最大值的最小值，最小值的最大值用二分
        # 最大值越小，操作越多；最大值越大，操作越小
        # 经典二分

        # 计算最大值为x时需要的操作数
        def cal_ops(x):
            '''x:单个袋子的最大值'''
            res = 0
            for num in nums:
                if num > x:
                    # 注意这里-1,例如6变3只用1次
                    res += (num - 1) // x
            return res
        
        l, r = 1, 10 ** 9
        # 最小都可成功即返回
        if cal_ops(l) <= maxOperations:
            return l
        
        # 经典二分
        while l < r:
            mid = l + (r - l) // 2
            if cal_ops(mid) <= maxOperations:
                # 可以让最大值更小一些
                r = mid
            else:
                # 必须让最大值更大
                l = mid + 1 # 因为mid已经凉凉
        
        return l # 返回的是最小的，所以是l

总结

最值的最值考虑二分
一般是一个函数具有某个单调性
然后二分x，得到最贴近最值的y