本文涉及的基础知识点

二分查找

题目

给你一个下标从 0 开始、长度为 n 的数组 usageLimits 。
你的任务是使用从 0 到 n - 1 的数字创建若干组，并确保每个数字 i 在 所有组 中使用的次数总共不超过 usageLimits[i] 次。此外，还必须满足以下条件：
每个组必须由 不同 的数字组成，也就是说，单个组内不能存在重复的数字。
每个组（除了第一个）的长度必须 严格大于 前一个组。
在满足所有条件的情况下，以整数形式返回可以创建的最大组数。
示例 1：
输入：usageLimits = [1,2,5]
输出：3
解释：在这个示例中，我们可以使用 0 至多一次，使用 1 至多 2 次，使用 2 至多 5 次。
一种既能满足所有条件，又能创建最多组的方式是：
组 1 包含数字 [2] 。
组 2 包含数字 [1,2] 。
组 3 包含数字 [0,1,2] 。
可以证明能够创建的最大组数是 3 。
所以，输出是 3 。
示例 2：
输入：usageLimits = [2,1,2]
输出：2
解释：在这个示例中，我们可以使用 0 至多 2 次，使用 1 至多 1 次，使用 2 至多 2 次。
一种既能满足所有条件，又能创建最多组的方式是：
组 1 包含数字 [0] 。
组 2 包含数字 [1,2] 。
可以证明能够创建的最大组数是 2 。
所以，输出是 2 。
示例 3：
输入：usageLimits = [1,1]
输出：1
解释：在这个示例中，我们可以使用 0 和 1 至多 1 次。
一种既能满足所有条件，又能创建最多组的方式是：
组 1 包含数字 [0] 。
可以证明能够创建的最大组数是 1 。
所以，输出是 1 。
参数范围：
1 <= usageLimits.length <= 105
1 <= usageLimits[i] <= 109

分析

知识点

假定最长组数为len，则各组长度一定是1,2…len。假定各组长度不是连续的，缺少x，那么将(x…) 都扔掉一个元素，变成[x,…)。持续这个过程至到各组长度连续为至。
只关心各值的数量，不关心值，比如：1,2,3和2,1,3完全相同。故可对数据进行排序。

二分

如果如果能创建n组，则一定能创建n-1组。随着len增加，一定会由能创建变成不能创建。寻找最后一个能创建的len。显然适合用左闭右开的二分。

判断能否创建len组

预处理

目标数组为{1,2…len}，源数组为升序排序后的 usageLimits，长度不足则在前面补0。比如：目标数组{1,2,3}，源数组{0,3,3}；目标数组{0,1,2,3}，{1,1,2,2}。

推理

我们用len数组表示目标数组，len[i]的含义，[0,len[i])都会有此元素。

长度为3

由于组内不能有重复元素，所以超过len个元素是无效的。我们用表格分析，那些情况刚好创建3组，没多余的数字。

猜测

3可以填4及以上缺，如：1333，{2},{3,4},{2,3,4},{1,2,3,4}

如何补缺

假定i1<i2，i2无法补i1的缺，因为i2已经用于[0,i2)不能用于[0,i1)中的任何组。
i1可以补i2的缺。i1只由于[0,i1)组，所以补[i2,…)的缺，不会造成同一组有重复数据。

一个数不会补缺两次

假定k = len[i2] -en[i1]，则i1多余不会超过k，
usageLimits[i1]-len[i1] >k
==>usageLimits[i1] >len[i1]+k
==>usageLimits[i1] >len[i2]
因为usageLimits[i2]>=usageLimits[i1]
所以：usageLimits[i2]>len2
所以：i2有多余，和有缺矛盾。
i1多余不会超过k，所以补完i2的缺就空了。
==>无需考虑一个数补两个缺

代码

核心代码

class Solution {
 public:
 int maxIncreasingGroups(vector& usageLimits) {
 m_c = usageLimits.size();
 m_v = usageLimits;
 sort(m_v.begin(), m_v.end());
 int left = 1, right = m_c + 1;
 while (right - left > 1)
 {
 const int mid = left + (right - left) / 2;
 if (Can(mid))
 {
 left = mid;
 }
 else
 {
 right = mid;
 }
 }
 return left;
 }
 bool Can(int len)
 {
 int i = m_c - 1;
 long long llNeed = 0;
 for (; len > 0; len–,i–)
 {
 llNeed -= (m_v[i] - len);
 if (m_v[i] >= len)
 {
 llNeed = max(0LL, llNeed);
 } 
 }
 for(;i >= 0 ; i–)
 {
 llNeed -= m_v[i];
 }
 return llNeed <= 0;
 }
 int m_c;
 vector m_v;
 };

测试用例

template
 void Assert(const T& t1, const T& t2)
 {
 assert(t1 == t2);
 }template
 void Assert(const vector& v1, const vector& v2)
 {
 if (v1.size() != v2.size())
 {
 assert(false);
 return;
 }
 for (int i = 0; i < v1.size(); i++)
 {
 Assert(v1[i] ,v2[i]);
 }
 }int main()
 {
 Solution slu;
 vector usageLimits;
 int res = 0;
 usageLimits = { 2,2,2 };
 res = slu.maxIncreasingGroups(usageLimits);
 Assert(res, 3);
 usageLimits = { 1,2,5 };
 res = slu.maxIncreasingGroups(usageLimits);
 Assert(res, 3);
 usageLimits = { 2,1,2 };
 res = slu.maxIncreasingGroups(usageLimits);
 Assert(res, 2);
 usageLimits = { 1,1 };
 res = slu.maxIncreasingGroups(usageLimits);
 Assert(res, 1);//CConsole::Out(res);}

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开

发环境： VS2022 C++17