leetcode: 1648. Color ball with decreasing sales value [Boundary find by two points]

分析

The idea is to find the biggest one every time
But the simulation times out
So dichotomous finds go to allnumthe number of balls needed
This number of balls cannot be exceededorders
Otherwise more balls
Then the extra ball is countednum的贡献
The rest of the arithmetic progressions can be summed

ac code

class Solution:
    def maxProfit(self, inventory: List[int], orders: int) -> int:
        MOD = 10 ** 9 + 7
        inventory.sort()
        n = len(inventory)

        def get_balls(num):
            # 所有大于num都变成numnumber of balls required
            idx = bisect_right(inventory, num) # 第一个大于num的
            cnt = 0
            for i in range(idx, n):
                cnt += inventory[i] - num
            return cnt

        l, r = 0, inventory[-1]
        while l + 1 < r:
            mid = (l + r) // 2
            if get_balls(mid) <= orders:
                r = mid
            else: 
                l = mid + 1
        
        ball1 = get_balls(r)
        ball2 = get_balls(l)
        ballFinal, numFinal = -1, -1
        if ball2 < orders:
            ballFinal, numFinal = ball2, l
        else:
            ballFinal, numFinal = ball1, r

        rest = orders - ballFinal
        ans = 0
        ans = numFinal * rest # rest
        idx = bisect_right(inventory, numFinal)
        for i in range(idx, n):
            ans += ((numFinal + 1 + inventory[i]) * (inventory[i] - numFinal) // 2)
        
        return ans % MOD

总结

二分找边界 + 等差数列