列表

详情

2234. 花园的最大总美丽值

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

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

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

请你返回 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可以让所有花园都变成完善的，但这样她的总美丽值反而更小。

 

提示：

原站题解

去查看

class Solution {
public:
long long maximumBeauty(vector<int>& flowers, long long newFlowers, int target, int full, int partial) {
}
};
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

rust 解法, 执行用时: 16 ms, 内存消耗: 3.5 MB, 提交时间: 2025-03-08 22:44:31 

impl Solution {

    pub fn maximum_beauty(mut flowers: Vec<i32>, new_flowers: i64, target: i32, full: i32, partial: i32) -> i64 {

        let n = flowers.len() as i64;

        let full = full as i64;

        let partial = partial as i64;



        // 如果全部种满，还剩下多少朵花？

        let mut left_flowers = new_flowers - target as i64 * n;

        for flower in &mut flowers {

            *flower = (*flower).min(target);

            left_flowers += *flower as i64; // 把已有的加回来

        }



        // 没有种花，所有花园都已种满

        if left_flowers == new_flowers {

            return n * full; // 答案只能是 n*full（注意不能减少花的数量）

        }



        // 可以全部种满

        if left_flowers >= 0 {

            // 两种策略取最大值：留一个花园种 target-1 朵花，其余种满；或者，全部种满

            return ((target - 1) as i64 * partial + (n - 1) * full).max(n * full);

        }



        flowers.sort_unstable(); // 时间复杂度的瓶颈在这，尽量写在后面



        let mut ans = 0;

        let mut pre_sum = 0;

        let mut j = 0;

        // 枚举 i，表示后缀 [i, n-1] 种满（i=0 的情况上面已讨论）

        for i in 1..=n as usize {

            // 撤销，flowers[i-1] 不变成 target

            left_flowers += (target - flowers[i - 1]) as i64;

            if left_flowers < 0 { // 花不能为负数，需要继续撤销

                continue;

            }



            // 满足以下条件说明 [0, j] 都可以种 flowers[j] 朵花

            while j < i && flowers[j] as i64 * j as i64 <= pre_sum + left_flowers {

                pre_sum += flowers[j] as i64;

                j += 1;

            }



            // 计算总美丽值

            // 在前缀 [0, j-1] 中均匀种花，这样最小值最大

            let avg = (left_flowers + pre_sum) / j as i64; // 由于上面特判了，这里 avg 一定小于 target

            let total_beauty = avg * partial + (n - i as i64) * full;

            ans = ans.max(total_beauty);

        }



        ans

    }

}

javascript 解法, 执行用时: 104 ms, 内存消耗: 71.8 MB, 提交时间: 2025-03-08 22:44:12 

/**

 * @param {number[]} flowers

 * @param {number} newFlowers

 * @param {number} target

 * @param {number} full

 * @param {number} partial

 * @return {number}

 */

var maximumBeauty = function(flowers, newFlowers, target, full, partial) {

    const n = flowers.length;



    // 如果全部种满，还剩下多少朵花？

    let leftFlowers = newFlowers - target * n; // 先减掉

    for (let i = 0; i < n; i++) {

        flowers[i] = Math.min(flowers[i], target);

        leftFlowers += flowers[i]; // 把已有的加回来

    }



    // 没有种花，所有花园都已种满

    if (leftFlowers === newFlowers) {

        return n * full; // 答案只能是 n*full（注意不能减少花的数量）

    }



    // 可以全部种满

    if (leftFlowers >= 0) {

        // 两种策略取最大值：留一个花园种 target-1 朵花，其余种满；或者，全部种满

        return Math.max((target - 1) * partial + (n - 1) * full, n * full);

    }



    flowers.sort((a, b) => a - b); // 时间复杂度的瓶颈在这，尽量写在后面



    let ans = 0, preSum = 0, j = 0;

    // 枚举 i，表示后缀 [i, n-1] 种满（i=0 的情况上面已讨论）

    for (let i = 1; i <= n; i++) {

        // 撤销，flowers[i-1] 不变成 target

        leftFlowers += target - flowers[i - 1];

        if (leftFlowers < 0) { // 花不能为负数，需要继续撤销

            continue;

        }



        // 满足以下条件说明 [0, j] 都可以种 flowers[j] 朵花

        while (j < i && flowers[j] * j <= preSum + leftFlowers) {

            preSum += flowers[j];

            j++;

        }



        // 计算总美丽值

        // 在前缀 [0, j-1] 中均匀种花，这样最小值最大

        const avg = Math.floor((leftFlowers + preSum) / j); // 由于上面特判了，这里 avg 一定小于 target

        const totalBeauty = avg * partial + (n - i) * full;

        ans = Math.max(ans, totalBeauty);

    }



    return ans;

};

golang 解法, 执行用时: 188 ms, 内存消耗: 8.8 MB, 提交时间: 2023-09-18 11:10:54 

func maximumBeauty(flowers []int, newFlowers int64, target, full, partial int) int64 {

    sort.Ints(flowers)

    n := len(flowers)

    if flowers[0] >= target { // 剪枝，此时所有花园都是完善的

        return int64(n * full)

    }



    leftFlowers := int(newFlowers) - target*n // 填充后缀后，剩余可以种植的花

    for i, f := range flowers {

        flowers[i] = min(f, target) // 去掉多余的花

        leftFlowers += flowers[i] // 补上已有的花

    }



    ans := 0

    for i, x, sumFlowers := 0, 0, 0; i <= n; i++ { // 枚举后缀长度 n-i

        if leftFlowers >= 0 {

            // 计算最长前缀的长度

            for ; x < i && flowers[x]*x-sumFlowers <= leftFlowers; x++ {

                sumFlowers += flowers[x] // 注意 x 只增不减，二重循环的时间复杂度为 O(n)

            }

            beauty := (n - i) * full // 计算总美丽值

            if x > 0 {

                beauty += min((leftFlowers+sumFlowers)/x, target-1) * partial

            }

            ans = max(ans, beauty)

        }

        if i < n {

            leftFlowers += target - flowers[i]

        }

    }

    return int64(ans)

}



func min(a, b int) int { if a > b { return b }; return a }

func max(a, b int) int { if a < b { return b }; return a }

cpp 解法, 执行用时: 216 ms, 内存消耗: 77.2 MB, 提交时间: 2023-09-18 11:10:23 

class Solution {

public:

    long long maximumBeauty(vector<int> &flowers, long long newFlowers, int target, int full, int partial) {

        sort(flowers.begin(), flowers.end());

        long n = flowers.size();

        if (flowers[0] >= target) return n * full; // 剪枝，此时所有花园都是完善的



        long leftFlowers = newFlowers - target * n; // 填充后缀后，剩余可以种植的花

        for (int i = 0; i < n; ++i) {

            flowers[i] = min(flowers[i], target); // 去掉多余的花

            leftFlowers += flowers[i]; // 补上已有的花

        }



        long ans = 0L, sumFlowers = 0L;

        for (int i = 0, x = 0; i <= n; ++i) { // 枚举后缀长度 n-i

            if (leftFlowers >= 0) {

                // 计算最长前缀的长度

                while (x < i && (long) flowers[x] * x - sumFlowers <= leftFlowers)

                    sumFlowers += flowers[x++]; // 注意 x 只增不减，二重循环的时间复杂度为 O(n)

                long beauty = (n - i) * full; // 计算总美丽值

                if (x) beauty += min((leftFlowers + sumFlowers) / x, (long) target - 1) * partial;

                ans = max(ans, beauty);

            }

            if (i < n) leftFlowers += target - flowers[i];

        }

        return ans;

    }

};

java 解法, 执行用时: 44 ms, 内存消耗: 56.3 MB, 提交时间: 2023-09-18 11:10:09 

class Solution {

    public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {

        Arrays.sort(flowers);

        long n = flowers.length;

        if (flowers[0] >= target) return n * full; // 剪枝，此时所有花园都是完善的



        var leftFlowers = newFlowers - target * n; // 填充后缀后，剩余可以种植的花

        for (var i = 0; i < n; ++i) {

            flowers[i] = Math.min(flowers[i], target); // 去掉多余的花

            leftFlowers += flowers[i]; // 补上已有的花

        }



        var ans = 0L;

        var sumFlowers = 0L;

        for (int i = 0, x = 0; i <= n; ++i) { // 枚举后缀长度 n-i

            if (leftFlowers >= 0) {

                // 计算最长前缀的长度

                while (x < i && (long) flowers[x] * x - sumFlowers <= leftFlowers)

                    sumFlowers += flowers[x++]; // 注意 x 只增不减，二重循环的时间复杂度为 O(n)

                var beauty = (n - i) * full; // 计算总美丽值

                if (x > 0) beauty += Math.min((leftFlowers + sumFlowers) / x, (long) target - 1) * partial;

                ans = Math.max(ans, beauty);

            }

            if (i < n) leftFlowers += target - flowers[i];

        }

        return ans;

    }

}

python3 解法, 执行用时: 616 ms, 内存消耗: 26.8 MB, 提交时间: 2023-09-18 11:09:54 

class Solution:

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

        flowers.sort()

        n = len(flowers)

        if flowers[0] >= target:  # 剪枝，此时所有花园都是完善的

            return n * full



        leftFlowers = newFlowers - target * n  # 填充后缀后，剩余可以种植的花

        for i in range(n):

            flowers[i] = min(flowers[i], target)  # 去掉多余的花

            leftFlowers += flowers[i]  # 补上已有的花



        ans, x, sumFlowers = 0, 0, 0

        for i in range(n + 1):  # 枚举后缀长度 n-i

            if leftFlowers >= 0:

                # 计算最长前缀的长度

                while x < i and flowers[x] * x - sumFlowers <= leftFlowers:

                    sumFlowers += flowers[x]

                    x += 1  # 注意 x 只增不减，二重循环的时间复杂度为 O(n)

                beauty = (n - i) * full  # 计算总美丽值

                if x:

                    beauty += min((leftFlowers + sumFlowers) // x, target - 1) * partial

                ans = max(ans, beauty)

            if i < n:

                leftFlowers += target - flowers[i]

        return ans

上一题

© 2025 leetcode.cn