[LeetCode] 每日一题 2234. 花园的最大总美丽值

题目链接

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

题目描述

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^5

• 1 <= flowers[i], target <= 10^5

• 1 <= newFlowers <= 10^10

• 1 <= full, partial <= 10^5

解题思路

这道题的核心是 贪心 + 二分查找，目标是在有限的 newFlowers 下，最大化所有花园的美丽值。由于 full 和 partial 可能导致不同的最优策略，我们可以分两种情况讨论：

1. 优先填满部分花园，使其达到 target

   • 我们按照花的数量 从小到大排序，然后 逆序遍历 数组，假设让后 n-i-1 个花园都变成完善花园（即填满到 target）

   • 剩余花园中，寻找一个最优的 min 值（即不完善花园的最小花数），使得该部分的得分 min * partial 最大化。这里使用 二分查找 进行优化

2. 填满所有花园，最多留一个 target-1 的花园

   • 如果 newFlowers 足够，我们可以直接填满所有花园，计算总美丽值 n * full

   • 但如果填满后仍有剩余，我们可以考虑留一个 target-1 的花园，使得 partial 贡献额外得分

整体采用 贪心策略，在保证 newFlowers 可行的情况下，尝试 不同的 full 和 partial 组合，从而获得最大美丽值

代码实现

class Solution {
    public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {
        int n = flowers.length;
        Arrays.sort(flowers);
        if (flowers[0] >= target) {
            return (long) full * n;
        }
        // 前缀和
        long[] sum = new long[n];
        sum[0] = flowers[0];
        for (int i = 1; i < n; i++) {
            sum[i] = sum[i - 1] + flowers[i];
        }
        long ans = 0;
        // 逆序遍历, 优先填满种花数多的花园
        for (int i = n - 1; i >= 0; i--) {
            if (flowers[i] >= target) {
                continue;
            }
            int left = flowers[0], right = target - 1;
            while (left < right) {
                int mid = (right - left + 1) / 2 + left;
                if (check(flowers, sum, newFlowers, mid, i)) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            ans = Math.max(ans, (long) (n - i - 1) * full + (long) left * partial);
            newFlowers -= target - flowers[i];
            if (newFlowers < 0) {
                return ans;
            }
        }
        if (newFlowers >= 0) {
            return Math.max(ans, (long) full * n);
        }
        return ans;
    }

    /**
     * 是否能用 newFlowers 把 flowers 里 [0, index] 的元素填充到 min
     */
    private boolean check(int[] flowers, long[] sum, long newFlowers, long min, int index) {
        int left = 0, right = index;
        // 查找最后一个小于 min 的元素位置 left
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (flowers[mid] < min) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return newFlowers >= min * (left + 1) - sum[left];
    }
}

复杂度分析

• 时间复杂度：O(n log n + n log target)，排序 O(n log n)，遍历和二分查找 O(n log target)

• 空间复杂度：O(n)，用于存储前缀和数组 sum

总结

这道题利用 贪心策略 结合 二分查找 进行优化，关键在于理解 full 和 partial 如何贡献美丽值。核心思路是：

1. 先尽量填满部分花园，同时找到 最小不完善花园 的最佳填充值

2. 遍历可能的填满数量，动态调整 newFlowers 分配方案

3. 二分查找最优 partial 贡献，确保 newFlowers 分配最优

本题我觉得重点就是对贪心策略的理解，与之前的一些简单题的不同之处在于，本题的策略有不同的分配方案，这是难点。然后针对排序数组进行查找操作，使用二分查找对查询效率进行优化是比较常规应该能很快想到的优化思路

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。