4815：[AHOI2018初中组] 分组

# [AHOI2018初中组] 分组

题目描述

小可可的学校信息组总共有 $n$ 个队员，每个人都有一个实力值 $a_i$。现在，一年一度的编程大赛就要到了，小可可的学校获得了若干个参赛名额，教练决定把学校信息组的 $n$ 个队员分成若干个小组去参加这场比赛。 但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队，于是要求分成的每个小组的队员实力值连续，同时，一个队不需要两个实力相同的选手。举个例子：$[1, 2, 3, 4, 5]$ 是合法的分组方案，因为实力值连续；$[1, 2, 3, 5]$ 不是合法的分组方案，因为实力值不连续；$[0, 1, 1, 2]$ 同样不是合法的分组方案，因为出现了两个实力值为 $1$ 的选手。 如果有小组内人数太少，就会因为时间不够而无法获得高分，于是小可可想让你给出一个合法的分组方案，满足所有人都恰好分到一个小组，使得人数最少的组人数最多，输出人数最少的组人数的最大值。 注意：实力值可能是负数，分组的数量没有限制。

输入格式

输入有两行： 第一行一个正整数 $n$，表示队员数量。 第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个队员的实力。

输出格式

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

7
4 5 2 3 -4 -3 -5

3

提示

### 样例解释 分为 $2$ 组，一组的队员实力值是 $[4, 5, 2, 3]$，一组是 $[-4, -3, -5]$，其中最小的组人数为 $3$，可以发现没有比 $3$ 更优的分法了。 ### 数据范围 对于 $100\%$ 的数据满足：$1\leq n\leq 10^5$，$|a_i|\leq10^9$。 本题共 $10$ 个测试点，编号为 $1\sim10$，每个测试点额外保证如下： | 测试点编号 | 数据限制 | | :-----------: | :-----------: | | $1\sim2$ | $n\leq 6, 1\leq a_i \leq 100$ | | $3\sim4$ | $n\leq 1000, 1\leq a_i\leq 10^5$ 且 $a_i$ 互不相同 | | $5\sim6$ | $n\leq 10^5$，$a_i$ 互不相同 | | $7\sim8$ | $n\leq 10^5, 1\leq a_i \leq10^5$ | | $9\sim 10$ | $n\leq 10^5, -10^9 \leq a_i \leq 10^9$ | 标签: P4447|贪心|2018|二分|安徽|队列

来源

P4447|[AHOI2018初中组] 分组