2495: 【普及+/提高】【P4447】分组
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
小可可的学校信息组总共有 个队员，每个人都有一个实力值 。现在，一年一度的编程大赛就要到了，小可可的学校获得了若干个参赛名额，教练决定把学校信息组的 个队员分成若干个小组去参加这场比赛。
但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队，于是要求分成的每个小组的队员实力值连续，同时，一个队不需要两个实力相同的选手。举个例子： 是合法的分组方案，因为实力值连续； 不是合法的分组方案，因为实力值不连续； 同样不是合法的分组方案，因为出现了两个实力值为 的选手。
如果有小组内人数太少，就会因为时间不够而无法获得高分，于是小可可想让你给出一个合法的分组方案，满足所有人都恰好分到一个小组，使得人数最少的组人数最多，输出人数最少的组人数的最大值。
注意：实力值可能是负数，分组的数量没有限制。
输入
输入有两行：
第一行一个正整数 ，表示队员数量。
第二行有 个整数，第 个整数 表示第 个队员的实力。
输出
输出一行，包括一个正整数，表示人数最少的组的人数最大值。
样例输入 复制
7
4 5 2 3 -4 -3 -5样例输出 复制
3提示
【样例解释】 分为 组，一组的队员实力值是 ，一组是 ，其中最小的组人数为 ，可以发现没有比 更优的分法了。
【数据范围】
对于 的数据满足：，。
本题共 个测试点，编号为 ，每个测试点额外保证如下：
| 测试点编号 | 数据限制 |
|---|---|
| 且 互不相同 | |
| 互不相同 | |
#include<bits/stdc++.h>
using namespace std;
struct team {
int begin;
int end;
int size;
}t[100010];
int a[100010];
int cmp(team t1,team t2) {
if (t1.size !=t2.size)
return t1.size<t2.size;
else
return t1.end<t2.end;
}
int main(){
int n,ans=0;
cin>>n;
for (int i=1;i<=n;i++) {
cin>>a[i];
}
sort(a+1,a+n+1);
int p=1;
t[p].begin=a[1];
t[p].end=a[1];
t[p].size=1;
for (int i=2;i<=n;i++) {
sort(t+1,t+p+1,cmp);
int k=1;
while (a[i]!=(t[k].end)+1 && k<=p) {
k++;
}
if (a[i]==(t[k].end)+1) {
(t[k].end)++;
(t[k].size)++;
}else {
p++;
t[p].begin=a[i];
t[p].end=a[i];
t[p].size=1;
}
}
sort(t+1,t+p+1,cmp);
ans=t[1].size;
cout<<ans<<endl;
return 0;
}