花园的最大总美丽值

2234. 花园的最大总美丽值

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⁵

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

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

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

上一题

下一题

详情