[AHOI2018初中组]分组

题目描述

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

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

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

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

输入格式

输入有两行：

第一行一个正整数 nnn，表示队员数量。
第二行有 nnn 个整数，第 iii 个整数 aia_iai​ 表示第 iii 个队员的实力。

输出格式

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

样例 #1

样例输入 #1

7
4 5 2 3 -4 -3 -5

样例输出 #1

3

提示

【样例解释】
分为 222 组，一组的队员实力值是 {4,5,2,3}\{4, 5, 2, 3\}{4,5,2,3}，一组是 {−4,−3,−5}\{-4, -3, -5\}{−4,−3,−5}，其中最小的组人数为 333，可以发现没有比 333 更优的分法了。

【数据范围】

对于 100%100\%100% 的数据满足：1≤n≤1000001\leq n\leq 1000001≤n≤100000，∣ai∣≤109|a_i|\leq10^9∣ai​∣≤109。

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

分析

1. 此题就是导弹拦截系统的升级版贪心问题，一个分组就是一个拦截系统，每个导弹拦截系统只能拦截和自己差值为1也就是连续的导弹，然后对于一个导弹，遍历cnt个导弹拦截系统，看看哪个可以容下他，只不过这题需要使用的系统是：用cnt个当中拦截过导弹数量最少的系统；可参考导弹拦截系统：1322：【例6.4】拦截导弹问题(Noip1999)——贪心
   

2. 样例分析：13
   -5 -5 -4 -4 -3 -3 2 3 3 4 4 4 5
   分组结果：
   -5 -4 -3
   -5 -4 -3
   2 3 4
   3 4
   4 5

3. 贪心策略：先排序，对于某个数a[i]，遍历cnt个已存在分组，看看a[i]是否和某个分组 j 匹配上（也就是和分组里面的元素值连续起来），可以的话，记录当前较优解，找拥有元素最少的分组，记录下他的分组编号minLenIdx，和元素个数minLen；然后遍历完cnt个分组，决定如何处理a[i]，是否重开一组还是放在编号minLenIdx的分组里面；

#includeusing namespace std;int n, ans = 100010;
int a[100010];
int cnt;//分组的个数
int last[100010];//分组的最后一个元素的值
int len[100010];//分组的长度int main() {cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}sort(a + 1, a + 1 + n);//先初始第一个分组last[++cnt] = a[1];len[cnt] = 1;for (int i = 2; i <= n; ++i) {int minLenIdx = -1;//拥有元素最少的分组编号int minLen = 100010;//拥有元素最少的分组的元素个数//遍历cnt个分组，看看可以放下哪个for (int j = 1; j <= cnt; j++) {if (a[i] - last[j] == 1) {//和第j个分组的元素连续if (len[j] < minLen) {//取拥有元素少的分组minLen = len[j];minLenIdx = j;}}}//处理a[i]if (minLenIdx == -1) {//需要新开一组last[++cnt] = a[i];len[cnt] = 1;} else {//填充在编号为minLenIdx组last[minLenIdx] = a[i];len[minLenIdx]++;}}for (int i = 1; i <= cnt; ++i) {ans = min(ans, len[i]);}cout << ans;return 0;
}