2234-花园的最大总美丽值

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:06 2023-09-13 17:01:06 Updated    

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 <= 105
  • 1 <= flowers[i], target <= 105
  • 1 <= newFlowers <= 1010
  • 1 <= full, partial <= 105

方法一：枚举「完善」和「不完善」的分界线

思路与算法

从贪心的角度，我们首先可以发现，最优的方案一定具有如下的形式：

我们选择数组 flowers 中最大的若干个元素，将它们加到至少 target 朵花，成为「完善」的花园；对于剩余的花朵，我们将它们加入 flowers 剩余的元素中，使得最终最小的元素尽可能大。

证明的方法也很简单，假设数组 flowers 中有两个元素 x, y 满足 x > y，我们一定是优先将 x 加到 target 的。这里可以使用反正 + 构造法，如果我们优先将 y 加到 target，那么添加的花朵数 target} - y 可以拆分成 target} - x 以及 x - y 这两部分之和，我们将前者添加到 x 中，后者添加到 y 中，这样最终同样得到了 target 和 x。因此优先将更大的元素加到 target 一定是优的。

因此我们可以将 flowers 首先进行降序排序。记其长度为 n，这样一来，我们可以枚举「完善」和「不完善」的分界线 i，表示将 [0, i) 变成完善的花园，[i, n) 为不完善的花园。

对于完善的部分，我们需要添加的花朵数量为：

\textit{target} \cdot i - \sum_{k=0}^{i-1} \textit{flowers}[k] \tag{1}

这个值需要小于等于 newFlowers。如果我们递增枚举 i，那么 (1) 式中的求和部分就是一个前缀和，我们可以很方便地进行维护。

记剩余可以添加的花的数目为 rest，有 rest} = \textit{newFlowers} - (1)。我们需要找到一个严格小于 target 的值，使得将所有剩余的花园的花的数量添加到至少为这个值时，添加的花朵总数小于等于 rest。我们可以将寻找这个值的过程分成两部分：第一步我们保证这个值一定在 flowers}[i .. n-1] 中出现，第二步我们再在这个值的基础上继续添加花朵。也就是说，我们需要找到一个下标 j 满足：

\textit{flowers}[j] \cdot (n-j) - \sum_{k=j}^{n-1} \textit{flower}[k] \leq \textit{rest} \tag{2}

并且：

\textit{flowers}[j-1] \cdot (n-j+1) - \sum_{k=j-1}^{n-1} \textit{flower}[k] > \textit{rest}

即我们需要找出的这个值在 \big[\textit{flowers}[j], \textit{flowers}[j-1]\big) 的范围内，因此我们就可以首先保证所有剩余的花园的花的数量都至少为 flowers}[j]，再继续对下标为 [j, n) 的花园平均地添加花朵，直到所有的花朵用完。在这一步中，下标为 [i, j) 的花园是不变的。

当我们递增地枚举 i 时，rest 是单调递减的，因此我们可以使用一个不断向右移动的指针来维护 j：即当 i 递增后，我们需要不断增加 j，直到 (2) 成立。在 j 递增的过程中，(2) 式中的求和部分是一个后缀和，我们可以很方便地进行维护。

当我们得到了当前的 i 对应的 j 之后，我们需要将 rest 减去 (2) 式左侧的值。下标为 [j, n) 的花园的数量为 n-j，因此我们还可以给每个花园添加 \lfloor \dfrac{\textit{rest} }{n-j} \rfloor 朵花，其中 \lfloor \cdot \rfloor 表示向下取整。

此时我们就能计算美丽值了。即为：

\textit{full} \cdot i + \textit{partial} \cdot \left( \min\left{ \textit{flowers}[j] + \lfloor \textit{rest} }{n-j} \rfloor, \textit{target} - 1 \right} \right)

细节

本题中没有规定 flowers 中的元素初始时一定小于等于 target，因此我们可以在一开始对其进行一次遍历，把所有大于 target 的元素都减小为 target。这样做也是合理的，显然我们没有必要给已经完善的花园再添加花朵。

同时在枚举 i 时，我们需要保证 [i, n) 对应的元素都严格小于 target，否则它们就不是不完善的了。由于数组已经按照降序排序，我们只需要验证是否有 flowers}[i] \neq \textit{target 即可。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    long long maximumBeauty(vector<int>& flowers, long long newFlowers, int target, int full, int partial) {
        int n = flowers.size();
        for (int& x: flowers) {
            x = min(x, target);
        }
        sort(flowers.begin(), flowers.end(), greater<int>());
        long long sum = accumulate(flowers.begin(), flowers.end(), 0LL);
        long long ans = 0;
        if (static_cast<long long>(target) * n - sum <= newFlowers) {
            ans = static_cast<long long>(full) * n;
        }

        long long pre = 0;
        int ptr = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                pre += flowers[i - 1];
            }
            if (flowers[i] == target) {
                continue;
            }
            long long rest = newFlowers - (static_cast<long long>(target) * i - pre);
            if (rest < 0) {
                break;
            }
            while (!(ptr >= i && static_cast<long long>(flowers[ptr]) * (n - ptr) - sum <= rest)) {
                sum -= flowers[ptr];
                ++ptr;
            }
            rest -= static_cast<long long>(flowers[ptr]) * (n - ptr) - sum;
            ans = max(ans, static_cast<long long>(full) * i + static_cast<long long>(partial) * (min(flowers[ptr] + rest / (n - ptr), static_cast<long long>(target) - 1)));
        }

        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:
        n = len(flowers)
        flowers = sorted([min(x, target) for x in flowers], reverse=True)
        total = sum(flowers)
        ans = 0
        
        if target * n - total <= newFlowers:
            ans = full * n
        
        pre = ptr = 0
        for i in range(n):
            if i != 0:
                pre += flowers[i - 1]
            if flowers[i] == target:
                continue
            
            rest = newFlowers - (target * i - pre)
            if rest < 0:
                break
            
            while not (ptr >= i and flowers[ptr] * (n - ptr) - total <= rest):
                total -= flowers[ptr]
                ptr += 1
            
            rest -= flowers[ptr] * (n - ptr) - total
            ans = max(ans, full * i + partial * (min(flowers[ptr] + rest // (n - ptr), target - 1)))
    
        return ans

复杂度分析

  • 时间复杂度：O(n \log n)。

  • 空间复杂度：O(\log n)，即为排序需要的栈空间。

 Comments
On this page
2234-花园的最大总美丽值