6040. 花园的最大总美丽值

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 。 贪心做法：我们首先把完整的花园剔除，然后往前枚举不完整的花园，不断把不完整的补完整并从中计算把剩余的补平均（且小于taget）时完美值，遍历找到其中最大的完美值。

class Solution {
public:
    long long maximumBeauty(vector<int>& flowers, long long newFlowers, int target, int full, int partial) {
       sort(flowers.begin(), flowers.end());
       long long cnt = 0;
       while(flowers.size() && flowers.back() >= target){
           flowers.pop_back();
           cnt++;
       }
       if(flowers.size() == 0) return cnt * full;
       long long sum = 0;
       for(int i = 0; i < flowers.size(); i++){
           sum += flowers[i];
       }
       long long T = target - 1, res = 0;
       for(int i = flowers.size(), j = i - 1; i >= 0; i--, cnt++){
           if(i < flowers.size()){
               newFlowers -= (target - flowers[i]);
           }
           if(newFlowers < 0) break;
           if(i > 0){
               while(j >= i){
                   sum -= flowers[j];
                   j--;
               }
               while((j + 1) * T - sum > newFlowers){
                   T--; // 从大便利的 最大平均值不会比这大了
                   while(flowers[j] >= T){
                       sum -= flowers[j];
                       j--;
                   }
               }
               res = max(res, full * cnt + partial * T);
           }else{
               res = max(res, full * cnt);
           }
       }
       return res;
    }
};