Leetcode 2234

题目要求

给定数组flowers ，每个元素可以增加，不能减少。 整数newFlowers 表示整个flowers的元素能增加的总和，对flowers进行操作后，最大化目标函数： full * 大于target的元素个数 + partial * 小于target的元素中的最小值

核心算法和原理

• 贪心：最大那些元素加到target，然后均匀增加最小的元素

• 对数组排序，问题转换为对后缀增加 & 对前缀的均匀增加

• 后缀 [i..n-1] 要加的数量

• 前缀[0..i]要加的数量avg

• i会随j递增而递增，存在单调性，考虑双指针维护这些变量

• 优化：特判了「可以全部加到target」和「不加也全都到target」的情况

代码

class Solution {
public:
    long long maximumBeauty(vector<int>& flowers, long long newFlowers,
                            int target, int full, int partial) {
        int n = flowers.size();
        long long ans = 0LL;
        // calculate the rest count of flowers if all planted to target
        long long leftFlower = newFlowers;
        for (int& flower : flowers) {
            flower = min(target, flower);
            leftFlower -= max(0, target - flower);
        }

        // There is no flower need to be planted
        if (leftFlower == newFlowers) {
            return 1LL * n * full;
        }

        // be able to planted to all-target
        if (leftFlower >= 0) {
            return max(1LL * n * full,
                       1LL * (n - 1) * full + 1LL * (target - 1) * partial);
        }

        ranges::sort(flowers);
        long long presum = 0;
        int i, j = 0;
        
        // leftFLower is currently the rest count when all gardens are complete
        for (i = 1; i <= n; i++) {
            leftFlower += target - flowers[i - 1];
            if (leftFlower >= 0) {
                while (j < i && 1LL * j * flowers[j] <= presum + leftFlower) {
                    presum += flowers[j];
                    j++;
                }

                if (j > 0) {
                    ans = max(ans, ((leftFlower + presum) * 1LL / j) * partial + 1LL * (n - i) * full);
                }
            }
        }
        return ans;
    }
};