题目描述

小可可的学校信息组总共有 n 个队员，每个人都有一个实力值 ai​。现在，一年一度的编程大赛就要到了，小可可的学校获得了若干个参赛名额，教练决定把学校信息组的 n 个队员分成若干个小组去参加这场比赛。

但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队，于是要求分成的每个小组的队员实力值连续，同时，一个队不需要两个实力相同的选手。举个例子：[1,2,3,4,5] 是合法的分组方案，因为实力值连续；[1,2,3,5] 不是合法的分组方案，因为实力值不连续；[0,1,1,2] 同样不是合法的分组方案，因为出现了两个实力值为 1 的选手。

如果有小组内人数太少，就会因为时间不够而无法获得高分，于是小可可想让你给出一个合法的分组方案，满足所有人都恰好分到一个小组，使得人数最少的组人数最多，输出人数最少的组人数的最大值。

注意：实力值可能是负数，分组的数量没有限制。

输入格式

输入有两行：

第一行一个正整数 n，表示队员数量。

第二行有 n 个整数，第 i 个整数 ai​ 表示第 i 个队员的实力。

输出格式

输出一行，包括一个正整数，表示人数最少的组的人数最大值。

输入输出样例

输入 #1复制

7
4 5 2 3 -4 -3 -5

输出 #1复制

3

说明/提示

样例解释

分为 2 组，一组的队员实力值是 [4,5,2,3]，一组是 [−4,−3,−5]，其中最小的组人数为 3，可以发现没有比 3 更优的分法了。

数据范围

对于 100% 的数据满足：1≤n≤105，∣ai​∣≤109。

本题共 10 个测试点，编号为 1∼10，每个测试点额外保证如下：

测试点编号	数据限制
1∼2	n≤6,1≤ai​≤100
3∼4	n≤1000,1≤ai​≤105 且 ai​ 互不相同
5∼6	n≤105，ai​ 互不相同
7∼8	n≤105,1≤ai​≤105
9∼10	n≤105,−109≤ai​≤109

思路：需要得到最后的分组策略中，含最小人数的要在所有分组策略中最多。那么意味着，如果我现在有多个分组的人具备x的实力值的人，此时来了一个x+1实力值的人，因为要最大化最少人数的拿个分组的人数，那么我们的贪心策略就是：要将此时这个x+1实力值的人放到当前人数最小的组中。

实现：由于每个组中的人的实力值需要连续且不重复，所以我们考虑对实力值进行排序。因为在来了一个新的数时，每个组都要被考虑是否放进去，判断条件：当前组中的最后一个数是否比当前数少一，在这个基础上，找出人数最少的那个组。所以我们需要维护每个组的状态，但是我们又不需要维护每个数，由于一开始对数组进行了排序，所以我们只需要维护每个组的最后一个数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;typedef struct Group{int x,y;bool operator<(Group g) const{return x<g.x;}	
}G;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;int nums[n];for(int i=0; i<n; i++) cin>>nums[i];sort(nums,nums+n);int q[n],qLen[n];int qnums = 0;for(int i=0; i<n; i++){int now = nums[i];int minLen = INT_MAX;int InsertIndex = -1; 		for(int j=0; j<qnums; j++){if(q[j]+1==now&&minLen>qLen[j]){minLen = qLen[j];InsertIndex = j;	}	}if(InsertIndex==-1){q[qnums] = now;qLen[qnums] = 1;qnums++;}else{q[InsertIndex]=now;qLen[InsertIndex]++;}}int minn = INT_MAX;for(int i=0; i<qnums; i++){minn = min(minn, qLen[i]);}cout<<minn<<endl;return 0;
}

但是，这样并不会通过所有的测试样例！！！！最后一个点会超时，我们考虑进行优化

可以发现我们每次都要找人数最少的那个组，那我们能不能搜索的再快一点呢？可以，直接使用二分搜索。

我们每次在找组的时候，都将此时这个数放到最右边的那个地方，这样我们就可以一直保证人数最少的会被变大。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;typedef struct Group{int x,y;bool operator<(Group g) const{return x<g.x;}	
}G;int bineray(int x,int l,int r,int *q){while(l<=r){int mid = l+(r-l)/2;if(q[mid]<=x) l=mid+1;else r=mid-1;}return q[l-1]==x?l-1:-1;
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;int nums[n];for(int i=0; i<n; i++) cin>>nums[i];sort(nums,nums+n);int q[n],qLen[n];int qnums = 0;for(int i=0; i<n; i++){int now = nums[i];int InsertIndex = bineray(now-1,0,qnums-1,q);if(InsertIndex==-1){q[qnums] = now;qLen[qnums] = 1;qnums++;}else{q[InsertIndex]=now;qLen[InsertIndex]++;}}int minn = INT_MAX;for(int i=0; i<qnums; i++){minn = min(minn, qLen[i]);}cout<<minn<<endl;return 0;
}