花园的最大总美丽值

难度: Hard

Alice 是 n 个花园的园丁，她想通过种花，最大化她所有花园的总美丽值。

给你一个下标从 0 开始大小为 n 的整数数组 flowers ，其中 flowers[i] 是第 i 个花园里已经种的花的数目。已经种了的花不能移走。同时给你 newFlowers ，表示 Alice 额外可以种花的 最大数目 。同时给你的还有整数 target ，full 和 partial 。

如果一个花园有至少 target 朵花，那么这个花园称为 完善的 ，花园的 总美丽值 为以下分数之和：

完善花园数目乘以 full.
剩余 不完善 花园里，花的 最少数目 乘以 partial 。如果没有不完善花园，那么这一部分的值为 0 。

请你返回 Alice 种最多 newFlowers 朵花以后，能得到的最大总美丽值。

示例 1：

输入：flowers = [1,3,1,1], newFlowers = 7, target = 6, full = 12, partial = 1
输出：14
解释：Alice 可以按以下方案种花
- 在第 0 个花园种 2 朵花
- 在第 1 个花园种 3 朵花
- 在第 2 个花园种 1 朵花
- 在第 3 个花园种 1 朵花
花园里花的数目为 [3,6,2,2] 。总共种了 2 + 3 + 1 + 1 = 7 朵花。
只有 1 个花园是完善的。
不完善花园里花的最少数目是 2 。
所以总美丽值为 1 * 12 + 2 * 1 = 12 + 2 = 14 。
没有其他方案可以让花园总美丽值超过 14 。

示例 2：

输入：flowers = [2,4,5,3], newFlowers = 10, target = 5, full = 2, partial = 6
输出：30
解释：Alice 可以按以下方案种花
- 在第 0 个花园种 3 朵花
- 在第 1 个花园种 0 朵花
- 在第 2 个花园种 0 朵花
- 在第 3 个花园种 2 朵花
花园里花的数目为 [5,4,5,5] 。总共种了 3 + 0 + 0 + 2 = 5 朵花。
有 3 个花园是完善的。
不完善花园里花的最少数目为 4 。
所以总美丽值为 3 * 2 + 4 * 6 = 6 + 24 = 30 。
没有其他方案可以让花园总美丽值超过 30 。
注意，Alice可以让所有花园都变成完善的，但这样她的总美丽值反而更小。

提示：

1 <= flowers.length <= 10⁵
1 <= flowers[i], target <= 10⁵
1 <= newFlowers <= 10¹⁰
1 <= full, partial <= 10⁵

Submission

运行时间: 192 ms

内存: 27.8 MB

class Solution:
    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:        
        # 第一步 预处理 先处理完善的
        q = [x for x in flowers if x < target]
        m, n = len(flowers), len(q)
        res = (m - n) * full
        if not q: return res
        if (n*target) <= (newFlowers+sum(q)):
            return res+(n-1)*full+max(full,(target-1)*partial)
        # 第二步 排序 需求前缀和
        #ans=0
        q.sort(reverse=True)
        acc = list(accumulate(q, initial=0))
        #need = list(accumulate([target - x for x in q], initial=0))

        # 第三步 枚举「完善」和「不完善」的分界线
        # 如果能全部完善，先按全完善计算
        ans = 0 # full * n if (n*target) <= (newFlowers+sum(q)) else 0
        #ans = full * n if need[n] <= newFlowers else 0

        j = 0 
        rest=newFlowers
        for i in range(n): # 完善 i 个
            if i>0:  
                rest -= target-q[i-1]
            if rest < 0: break
            # 确定补齐的个数 n - j 随着 i 增加，j 在原来的基础上增加
            while i>j or (x := q[j] * (n - j) - acc[n] + acc[j]) > rest:
                j += 1
            
            x = rest-x
            x = min(target - 1, q[j] + x // (n - j)) # q[j] + 剩余平均
            ans = max(ans, full * i + partial * x)

        return res + ans

Explain

这个问题的解法涉及到排序和贪心策略。首先，我们将所有已经达到或超过目标花朵数的花园筛选出来，这些花园已经是'完善的'。对于剩余的花园，我们将其排序并尝试通过添加花朵来使得更多的花园成为'完善的'。我们从没有达到目标的花园列表中，从最需要花朵最少的开始，尝试通过增加花朵使其达到或超过目标花朵数。通过枚举可能的完善花园数，我们可以计算出每种情况下的美丽值，并更新最大值。关键点在于动态地调整剩余花朵的分配，以及如何计算在某种分配下的最小不完善花园中的花朵数。

时间复杂度: O(n log n) + O(n^2) = O(n^2)

空间复杂度: O(n)

class Solution:
    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:        
        # 筛选出未达标的花园
        q = [x for x in flowers if x < target]
        m, n = len(flowers), len(q)
        # 计算已完善花园的美丽值
        res = (m - n) * full
        # 如果没有不完善的花园，直接返回
        if not q: return res
        # 如果新增花朵足以使所有花园完善
        if (n*target) <= (newFlowers+sum(q)):
            return res+(n-1)*full+max(full,(target-1)*partial)
        # 对未达标花园进行排序
        q.sort(reverse=True)
        # 计算前缀和
        acc = list(accumulate(q, initial=0))
        # 初始化答案
        ans = 0 
        j = 0 
        rest=newFlowers
        # 枚举完善花园的数量
        for i in range(n): 
            if i>0:  
                rest -= target-q[i-1]
            if rest < 0: break
            # 调整j以满足剩余花朵数条件
            while i>j or (x := q[j] * (n - j) - acc[n] + acc[j]) > rest:
                j += 1
            # 计算最小不完善花园的花朵数
            x = rest-x
            x = min(target - 1, q[j] + x // (n - j)) 
            # 更新最大美丽值
            ans = max(ans, full * i + partial * x)
        # 返回总美丽值
        return res + ans

Explore

在题解中，`筛选出未达标的花园`是基于花园当前的花朵数是否达到了设定的目标花朵数`target`。如果一个花园的花朵数量小于`target`，则这个花园被认为是未达标的。这样的筛选是为了将注意力集中在那些需要额外添加花朵以达标的花园上，从而优化花朵的分配和使用策略。

在题解中选择逆序排序（从大到小排序）是为了优化花朵的分配过程。通过先处理那些离达标差距较小的花园，可以更高效地使用新增的花朵。逆序排序确保了在每一步尝试完善花园时，我们都尽可能地接近目标，从而可能减少需要的总花朵数。如果采用正序排序，则可能导致在处理花朵需求较大的花园时，已经没有足够的花朵来满足需求，从而影响总体的策略效率。

题解中实现`枚举可能的完善花园数`的方法是逐一尝试每个可能的花园数量，并计算在这种情况下的最大美丽值。关键步骤包括：1. 从0开始，逐个增加完善的花园数量，同时递减剩余可用的花朵数。2. 更新剩余花朵数后，检查是否有足够的花朵来继续增加完善的花园数量。3. 调整索引`j`，确保剩余的花朵数足以至少保持当前的完善花园数。4. 计算在当前完善花园数下，最小的不完善花园可以达到的花朵数，并据此更新可能的最大美丽值。这种枚举和调整的过程允许动态地评估不同完善花园数量下的美丽值，找到最优解。