Leetcode 2234. Maximum Total Beauty of the Gardens

[Woodyiiiiiii]

这道题的难点在于如何计算公式/规划数组。

我想DP/二分肯定都不可以。那么这道题就是要尽可能遍历所有可能了，考虑到复杂度，就只能是排序/贪心/双指针了。

首先，对花排序，然后计算使用完newflowers的最大情况，索引记录为指针p1，然后做一下判断，如果p1<0，说明可以全部满足target，所以两种情况选最大的；接着是遍历所有可能了，从最小的花朵数量minF判断，设指针p2=0，移动p1/p2指针，如果flowers不够，则从[p1,n]范围内的花去取newflowers，观察p1是否超过数组长度从而判断是否能够满足当前最小的花朵数量，然后依次增加最小花朵数量minF。

复杂的地方在于while(minF<target)循环内。

class Solution {
    public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {
        // sort flowers in descending order
        Arrays.sort(flowers);
        int n = flowers.length;
        int p1 = n - 1;
        System.out.println(n);

        for (; p1 >= 0; p1--) {
            if (Math.max(0, target - flowers[p1]) > newFlowers) {
                break;
            }
            newFlowers -= Math.max(0, target - flowers[p1]);
        }
        if (p1 == -1) {
            return Math.max((long) n * full, flowers[0] == target ? (long) n * full : (long) (n - 1) * full + (long) partial * (target - 1));
        }

        int p2 = 0;
        long minF = flowers[p2], sum = 0, ans = 0;
        while (minF < target) {
            while (p2 <= p1 && flowers[p2] <= minF)
                sum += flowers[p2++];
            long needed = p2 * minF - sum;
            if (needed > newFlowers) {
                if (++p1 >= n)
                    break;
                newFlowers += Math.max(0, target - flowers[p1]);
            }
            else {
                ans = Math.max((long) (n - p1 - 1) * full + (minF * partial), ans);
                ++minF;
            }
        }
        return ans;
    }
}

---

• 2234. Maximum Total Beauty of the Gardens