2234. Maximum Total Beauty of the Gardens

link

Start from 2233 Maximum Product After K Increments

1. pop up all the complete garden and store result in res0

2. start from the right, try to make minimum number higher. Then fill the right. res = each iteration result

class Solution:
    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:

        flowers.sort()

        res0 = 0

        while flowers and flowers[-1] >= target:
            res0 += full
            flowers.pop()

        n = len(flowers)

        if n == 0:
            return res0

        preSum = [0] * n
        preSum[0] = flowers[0]
        diff = [0] * n

        for i in range(1, n):
            preSum[i] = preSum[i-1] + flowers[i]

        for i in range(1, n):
            diff[i] = flowers[i] * (i+1) - preSum[i]

        

        res1 = 0

        for i in range(n - 1, -1, -1):
            
            idx = bisect.bisect_right(diff, newFlowers, lo=0, hi=i+1)
            
            
            total = preSum[idx-1] + newFlowers
            each = min(target - 1, total // idx)

            res1 = max(res1, (n-1-i) * full + each * partial)


            newFlowers -= target - flowers[i]

            # can't fill the current flowers[i] to complete garden, break
            if newFlowers < 0:
                break
        
        if newFlowers >= 0:
            res1 = max(res1, n * full)

        
        return res0 + res1