leetcode：1760. The least number of goal balls in the bag [the most valuable value + the scoreboard]

analysis

The best value can be considered as two points
Find monotonicity ！！！
How to find ？
Let's analyze
If the maximum value of a single bag ball is larger , Is it true that the smaller the number of operations ？
conversely , The smaller the maximum , Is it the bigger the operation ;
We build a function that can calculate the minimum number of operations by giving the maximum value of a single bag
Then we ask for the minimum and maximum
So we judge cal_ops(mid)
If this value is less than or equal to maxOps, It indicates that the maximum value can be smaller , therefore r take mid, Can succeed
conversely , If it is greater than maxOps, Too many operands , Indicate that the maximum value should be increased , here mid It's cool
So we need to l = mid + 1
Finally, it returns the minimum value, so it returns l

ac code

class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        #  The minimum of the maximum , The maximum value of the minimum value is divided into two 
        #  The smaller the maximum , The more operations ; The greater the maximum , The smaller the operation 
        #  Classic dichotomy 

        #  The calculated maximum value is x Operands required when 
        def cal_ops(x):
            '''x: Maximum value of a single bag '''
            res = 0
            for num in nums:
                if num > x:
                    #  Note that there -1, for example 6 change 3 Only 1 Time 
                    res += (num - 1) // x
            return res
        
        l, r = 1, 10 ** 9
        #  The smallest can be successful and return 
        if cal_ops(l) <= maxOperations:
            return l
        
        #  Classic dichotomy 
        while l < r:
            mid = l + (r - l) // 2
            if cal_ops(mid) <= maxOperations:
                #  You can make the maximum value smaller 
                r = mid
            else:
                #  The maximum value must be made larger 
                l = mid + 1 #  because mid It's cool 
        
        return l #  The returned is the smallest , So it is l

summary

The best value is considered as two points
Generally, a function has some monotonicity
Then two points x, Get the closest and most valuable y