转摘长度递增组的最大数目

隋问风阅读量 10

给你一个下标从 0 开始、长度为 n 的数组 usageLimits 。

你的任务是使用从 0 到 n - 1 的数字创建若干组，并确保每个数字 i 在 所有组 中使用的次数总共不超过 usageLimits[i] 次。此外，还必须满足以下条件：

  • 每个组必须由 不同 的数字组成，也就是说，单个组内不能存在重复的数字。
  • 每个组（除了第一个）的长度必须 严格大于 前一个组。

在满足所有条件的情况下，以整数形式返回可以创建的最大组数。

1. 贪心 + 排序+ 数学

对于排序数组，我们只需找到诸如123456的排列，便可使得组的分配增加
即当前数字大于对应位所需的数，可使得组增加
同时，假如前面的数不足以构造新的组，后面的数可以与前面合并，以满足组的要求
所以在决定新的组能形成与否的时候，只需判断总量大于对应组大小最基础的总量即可

思考：有没有可能存在总量大于基础值，对应位的量小于对应值，不能形成新的组的情况
即前面有组拉高了总量，而当前值小于应有值，比如123333
可以证明不可能存在该情况
假使数的个数与组一致，前面假使有数拉高总量，由于是非递减数列，当前数必然满足对应位要求
假使数的个数大于组的个数，多出的数可以灵活分配给原来的组和新的组，使恰好满总每个组的要求（是否能错开避免重复？）

复制代码 
class Solution {
public:
    int maxIncreasingGroups(vector<int>& usageLimits) {
        sort(usageLimits.begin(),usageLimits.end());
        long long  res = 0;
        long long  s = 0;
        for(auto num:usageLimits){
            s+=num;
            if(s>=(res+1)*(res+2)/2)//尝试分配下一个组，满足要求则添加
                res += 1;
        }
        return res;
    }
};



    ===========================
    【来源： 博客园】
    【作者： 失控D大白兔】
    【原文链接】 https://www.cnblogs.com/929code/p/17576305.html
    声明：转载此文是出于传递更多信息之目的。若有来源标注错误或侵犯了您的合法权益，请作者持权属证明与本网联系，我们将及时更正、删除，谢谢。
标签： 满足usageLimits大于数字要求
0/300
全部评论0
0/300