题目：2234. 花园的最大总美丽值 - 力扣（LeetCode）

1. 先对flowers进行升序排序，计算现有“完善花园”的数量minFull；如果没有，minFull为n。

2. 计算前缀和f[]。

3. 从i=(minFull-1 to 0)枚举从第i个开始的花园都变成“完善花园”后剩余的花的数量，计算剩余的花可以使最小值最大的值

4. 因为我们是倒序枚举的，设“非完善花园”的最小数量是flowers[j]，则j在美剧过程中一定不会增长，可以通过f[]和剩余的花的数量快速计算出是否可以满足“非完善花园”的最小数量是flowers[j]这一条件；如果满足该条件后花朵数量还有剩余，可以计算可以给所有“非完善花园”各增加多少朵花

O(nlog(n))的排序+O(n)的遍历就可以得到答案了：

class Solution {
public:long long maximumBeauty(vector<int>& flowers, long long newFlowers, int target1, int full1, int partial1) {long long target = target1;long long full = full1;long long partial = partial1;sort(flowers.begin(), flowers.end());long long n = flowers.size();long long* f = new long long[n];if (flowers[0] >= target) {return full * n;}f[0] = flowers[0];long long minFull = n;for (int i = 1; i < n; i++) {f[i] = flowers[i];f[i] += f[i - 1];if (flowers[i] >= target) {minFull = i;break;}}long long ret = 0;long long j = minFull - 1;long long flowerJ = flowers[j];long long score, remain, temp;for (long long i = minFull - 1; i >= 0; i--) {if (j > i) {j = i;flowerJ = flowers[j];}while (j >= 0 && f[j] + newFlowers < flowerJ * (j + 1)) {j--;flowerJ = flowers[j];}remain = newFlowers - (flowerJ * (j + 1) - f[j]);temp = flowerJ + remain / (j + 1);if (temp >= target) {temp = target - 1;}score = (n - 1 - i) * full + temp * partial;if (score > ret) {ret = score;}newFlowers -= (target - flowers[i]);if (newFlowers < 0) {break;}}if (newFlowers >= 0) {score = n * full;if (score > ret) {ret = score;}}return ret;}
};