2234. 花园的最大总美丽值

Hard

题目描述

Alice 是 n 个花园的管理员，她想种花来最大化所有花园的总美丽值。

给你一个下标从 0 开始的整数数组 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。

示例 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。

约束条件：

1 <= flowers.length <= 10^5
1 <= flowers[i], target <= 10^5
1 <= newFlowers <= 10^10
1 <= full, partial <= 10^5

解题思路

这是一道复杂的贪心优化问题，需要巧妙地结合排序、前缀和和二分查找。

核心思路：

枚举完整花园数量：我们可以枚举有 k 个完整花园，然后计算剩余花朵能让不完整花园达到的最大最小值
贪心选择：要让 k 个花园变完整，应该优先选择花朵数量最多的 k 个花园，这样消耗的新花朵最少
二分优化最小值：对于剩余的不完整花园，用二分查找来找到能达到的最大最小花朵数

详细步骤：

首先对花园排序，方便贪心选择
预计算前缀和，快速计算将前 i 个花园都提升到某个水平需要的花朵数
枚举完整花园数量 k（从 0 到 n），对于每个 k：
- 计算让最大的 k 个花园变完整需要的花朵数
- 如果花朵不够，跳过这种情况
- 用二分查找剩余花朵能让不完整花园达到的最大最小值
- 计算总美丽值并更新答案

时间复杂度分析： 外层枚举 O(n)，内层二分查找 O(log target)，总体 O(n log target)

代码实现

class Solution {
public:
    long long maximumBeauty(vector<int>& flowers, long long newFlowers, int target, int full, int partial) {
        int n = flowers.size();
        sort(flowers.begin(), flowers.end());
        
        // 预处理：计算前缀和
        vector<long long> prefix(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + flowers[i];
        }
        
        // 计算需要多少花朵让最右边的k个花园变完整
        auto getCost = [&](int k) -> long long {
            if (k == 0) return 0;
            long long cost = 0;
            for (int i = n - k; i < n; i++) {
                cost += max(0, target - flowers[i]);
            }
            return cost;
        };
        
        // 二分查找：给定剩余花朵数，能让前left个花园达到的最大最小值
        auto getMaxMin = [&](int left, long long remaining) -> int {
            if (left == 0) return 0;
            int low = flowers[0], high = target - 1;
            int result = flowers[0];
            
            while (low <= high) {
                int mid = low + (high - low) / 2;
                long long needed = 0;
                for (int i = 0; i < left; i++) {
                    needed += max(0, mid - flowers[i]);
                }
                if (needed <= remaining) {
                    result = mid;
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            return result;
        };
        
        long long maxBeauty = 0;
        
        // 枚举完整花园数量
        for (int k = 0; k <= n; k++) {
            long long costForComplete = getCost(k);
            if (costForComplete > newFlowers) break;
            
            long long remaining = newFlowers - costForComplete;
            int incompleteCount = n - k;
            
            if (incompleteCount == 0) {
                maxBeauty = max(maxBeauty, (long long)k * full);
            } else {
                int minFlowers = getMaxMin(incompleteCount, remaining);
                long long beauty = (long long)k * full + (long long)minFlowers * partial;
                maxBeauty = max(maxBeauty, beauty);
            }
        }
        
        return maxBeauty;
    }
};

class Solution:
    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:
        n = len(flowers)
        flowers.sort()
        
        # 计算前缀和
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + flowers[i]
        
        def get_cost(k):
            """计算让最右边k个花园变完整的花朵数"""
            if k == 0:
                return 0
            cost = 0
            for i in range(n - k, n):
                cost += max(0, target - flowers[i])
            return cost
        
        def get_max_min(left, remaining):
            """二分查找：给定剩余花朵数，前left个花园能达到的最大最小值"""
            if left == 0:
                return 0
            low, high = flowers[0], target - 1
            result = flowers[0]
            
            while low <= high:
                mid = (low + high) // 2
                needed = 0
                for i in range(left):
                    needed += max(0, mid - flowers[i])
                
                if needed <= remaining:
                    result = mid
                    low = mid + 1
                else:
                    high = mid - 1
            
            return result
        
        max_beauty = 0
        
        # 枚举完整花园数量
        for k in range(n + 1):
            cost_for_complete = get_cost(k)
            if cost_for_complete > newFlowers:
                break
            
            remaining = newFlowers - cost_for_complete
            incomplete_count = n - k
            
            if incomplete_count == 0:
                max_beauty = max(max_beauty, k * full)
            else:
                min_flowers = get_max_min(incomplete_count, remaining)
                beauty = k * full + min_flowers * partial
                max_beauty = max(max_beauty, beauty)
        
        return max_beauty

public class Solution {
    public long MaximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {
        int n = flowers.Length;
        Array.Sort(flowers);
        
        // 计算让最右边k个花园变完整的花朵数
        Func<int, long> getCost = (k) => {
            if (k == 0) return 0;
            long cost = 0;
            for (int i = n - k; i < n; i++) {
                cost += Math.Max(0, target - flowers[i]);
            }
            return cost;
        };
        
        // 二分查找：给定剩余花朵数，前left个花园能达到的最大最小值
        Func<int, long, int> getMaxMin = (left, remaining) => {
            if (left == 0) return 0;
            int low = flowers[0], high = target - 1;
            int result = flowers[0];
            
            while (low <= high) {
                int mid = low + (high - low) / 2;
                long needed = 0;
                for (int i = 0; i < left; i++) {
                    needed += Math.Max(0, mid - flowers[i]);
                }
                
                if (needed <= remaining) {
                    result = mid;
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            return result;
        };
        
        long maxBeauty = 0;
        
        // 枚举完整花园数量
        for (int k = 0; k <= n; k++) {
            long costForComplete = getCost(k);
            if (costForComplete > newFlowers) break;
            
            long remaining = newFlowers - costForComplete;
            int incompleteCount = n - k;
            
            if (incompleteCount == 0) {
                maxBeauty = Math.Max(maxBeauty, (long)k * full);
            } else {
                int minFlowers = getMaxMin(incompleteCount, remaining);
                long beauty = (long)k * full + (long)minFlowers * partial;
                maxBeauty = Math.Max(maxBeauty, beauty);
            }
        }
        
        return maxBeauty;
    }
}

var maximumBeauty = function(flowers, newFlowers, target, full, partial) {
    const n = flowers.length;
    flowers.sort((a, b) => a - b);
    
    // Calculate cost to make first i gardens complete
    const completeCosts = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        completeCosts[i + 1] = completeCosts[i] + Math.max(0, target - flowers[n - 1 - i]);
    }
    
    let maxBeauty = 0;
    
    // Try different numbers of complete gardens
    for (let complete = 0; complete <= n; complete++) {
        const costForComplete = completeCosts[complete];
        if (costForComplete > newFlowers) break;
        
        const remainingFlowers = newFlowers - costForComplete;
        const incompleteCount = n - complete;
        
        if (incompleteCount === 0) {
            maxBeauty = Math.max(maxBeauty, complete * full);
            continue;
        }
        
        // Binary search for maximum minimum flowers in incomplete gardens
        let left = flowers[0];
        let right = target - 1;
        let maxMin = flowers[0];
        
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            let cost = 0;
            
            for (let i = 0; i < incompleteCount; i++) {
                if (flowers[i] < mid) {
                    cost += mid - flowers[i];
                }
            }
            
            if (cost <= remainingFlowers) {
                maxMin = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        maxBeauty = Math.max(maxBeauty, complete * full + maxMin * partial);
    }
    
    return maxBeauty;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度值	说明
时间复杂度	O(n log target)	外层枚举O(n)，内层二分查找O(log target)
空间复杂度	O(1)	只使用常数额外空间（不考虑排序的空间）

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目