题目

Description

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

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

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

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

Input

输入有两行：

第一行一个正整数 nn，表示队员数量。
第二行有 nn 个整数，第 ii 个整数 aiai​ 表示第 ii 个队员的实力。

Output

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

Sample Input

7
4 5 2 3 -4 -3 -5

Sample Output

3

思路

因为实力要连续，所以先把实力从小到大排序；

然后用多个队列来储存分组情况；

枚举当前人的实力，如果存在队列使得当前实力与队列尾元素是连续的，则入队；

否则就新开一个队列来存储；

注意如果实力有相同，如 $1$, $2$, $2$ ,$3$ ；

如果顺序遍历每个队列则最后结果为

$q1$: $1$  $2$  $3$  ;

$q2$: $2$ ;

不是最佳分组；

所以，遍历队列时，逆序枚举就可以避免这种情况；

可优化点：

如果当前实力大于所有队列的尾元素$+1$的时候；

我们在新开队列的同时，不在枚举之前的所有队列；

因为我们把实力排为递增序列，所以之后的实力大于所有队列尾元素$+1$，不可能入队；

代码

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 3 using namespace std;
 4 const ll _=1e5+1;
 5 ll n,m;
 6 ll a[_];
 7 queue<ll> q[_];
 8 int main()
 9 {
10     cin>>n;
11     for(ll i=1;i<=n;i++)
12         cin>>a[i];
13     sort(a+1,a+n+1);//实力排升序
14     ll pre=1;//初始上一个可遍历的队列
15     m=1; q[1].push(a[1]);//初始化
16     for(ll i=2;i<=n;i++)
17     {
18         ll flag=0,t=1;//flag记录当前实力是否能接到某个队列后面
19                       //t记录是否当前实力大于所有队尾+1的值
20         for(ll j=m;j>=pre;j--)//倒序遍历
21         if(a[i]<=q[j].back()+1)
22         {
23             t=0;
24             if(a[i]==q[j].back()+1)
25             {
26                 flag=1;
27                 q[j].push(a[i]);
28                 break;
29             }
30         }
31         if(!flag)
32         {//如果不能接到其他队列，则新开队列记录分组
33             q[++m].push(a[i]);
34             if(t) pre=m;//如果当前实力大于所有队尾+1
35             //更新可遍历的队列
36         }
37             
38     }
39     ll minn=n;
40     for(ll i=1;i<=m;i++)
41     {
42         ll x=q[i].size();
43         minn=min(minn,x);
44     }
45     cout<<minn;
46     return 0;
47 }