题目描述

小可可的学校信息组总共有 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≤100000，∣ai​∣≤109。

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

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

思路：

我自己写只过了一半的测试点，后面实在没思路，参考了网上的解题思路，第一遍在遍历现有组选择符合的组加入元素时，选择遍历所有的组，这显然有些冗余，很多组的遍历是不必要的，因为只允许相邻元素相差1，那么后面的组增长起来后，前面的组就作废了（即不可能再加入新的元素），提交之后显然有一个测试点没过，因为超时了。

由于不知道如何确定下界，随便调了个p-5，居然AC了。。其中的原理还不清楚，等过几天再回来看看说不定有新的思路。

AC代码：

//思路：每张牌我们把他放到上一张比他小1的那个组，优先选择放牌的数量小的那个组（贪心：确保最终牌数最小的组的牌数尽可能大），没有可以放的组就重开一个。
#include <bits/stdc++.h>
using namespace std;

#define Init 100005
struct group {
	long long int next;//表示该组期待的下一个元素值，等于该值才能加入该组
	int len = 0;//存放该组的当前元素个数
}f[Init];

bool cmp(group x, group y)
{
	return x.len < y.len;
}

int main()
{
	long long int a[Init];
	int n, p = 0;//n为元素个数，p为当前存在的组数-1，即最后一个组的下标
	cin >> n;
	for (int i = 0;i < n;i++)
	{
		cin >> a[i];
	}
	sort(a, a + n);
	//先把第一个元素放入一个组别中
	f[0].next = a[0] + 1;
	f[0].len = 1;
	//核心思路，遍历排序后的每一个元素，将其加入所属组别或新建组
	for (int i = 1;i < n;i++)
	{
		bool flag = 1;//标记该元素是否找到现有的可加入的组，如果没找到，需要新开一个组

		for (int j = p;j >= p-5;j--)
		{//p倒序遍历即可保证优先加入数量最少的组
			if (a[i] == f[j].next) {//符合条件，加入该组
				f[j].next++;
				f[j].len++;
				flag = 0;//已加入
				break;//找到组别即可推出当前循环，去找下一个数所属组别
			}
		}

		//如果遍历完所有的现有组都没有找到可加入的，则需要为该元素新开一个组
		if (flag)
		{
			//开一个新组
			p++;
			//将该元素放入新组别中
			f[p].next = a[i] + 1;
			f[p].len = 1;
		}
	}
	sort(f, f + p + 1, cmp);
	cout << f[0].len;
	return 0;
}