LC 6040. 花园的最大总美丽值

https://leetcode-cn.com/problems/maximum-total-beauty-of-the-gardens/

这个题目的核心是一个最优均分方案。对于full garden比较好办，直接进行枚举就行，如何对于partial garden最优化均分方案呢？这个可以是个线性的过程。

假设我们需要在 `X[1…n]` 寻找最优均分方案，并且假设还有K个flowers可以分配：

我们可以假设如果最优值至少是 `X[1]`, 那么需要分配 `K - ACC[1]` 个，可以将K个flowers分配到最前面1个元素
如果最优值至少是 `X[2]`, 那么需要分配 `K-ACC[2]` 个，我们可以将K个flowers分配到最前面2个元素
以此类推，其中ACC是这个X的前缀和。我们寻找最多能分配多个元素，假设j个元素，那么至少可以将 `X[1..j]` 都提升到 `X[j]` 的水平。

class Solution:
    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:
        base = full * len([x for x in flowers if x >= target])

        flowers = [x for x in flowers if x < target]
        flowers.sort()
        n = len(flowers)
        acc = [0] * (n + 1)
        for i in range(n):
            acc[i + 1] = acc[i] + flowers[i]

        j = 0
        ans = 0
        for i in range(n + 1):
            k = newFlowers - ((n - i) * target - (acc[n] - acc[i]))
            if k < 0:
                continue

            while j < i:
                fill = flowers[j] * (j + 1) - acc[j + 1]
                if fill > k:
                    break
                j += 1

            # full (n-i)
            # partial can be covered up to j elements.
            x = 0 if j == 0 else (acc[j] + k) // j
            if j < i:
                assert x < flowers[j]
            x = min(x, target - 1)
            value = full * (n - i) + x * partial
            ans = max(ans, value)

        return ans + base