#P4447. [AHOI2018初中组] 分组

    ID: 2187 Type: RemoteJudge 1000ms 128MiB Tried: 3 Accepted: 2 Difficulty: 10 Uploaded By: Tags>贪心2018二分答案安徽队列

[AHOI2018初中组] 分组

题目描述

小可可的学校信息组总共有 nn 个队员,每个人都有一个实力值 aia_i。现在,一年一度的编程大赛就要到了,小可可的学校获得了若干个参赛名额,教练决定把学校信息组的 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 的选手。

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

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

输入格式

输入有两行:

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

输出格式

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

7
4 5 2 3 -4 -3 -5
3

提示

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

【数据范围】

对于 100%100\% 的数据满足:1n1000001\leq n\leq 100000ai109|a_i|\leq10^9

本题共 1010 个测试点,编号为 1101\sim10,每个测试点额外保证如下: | 测试点编号 | 数据限制 | | :-----------: | :-----------: | | 121\sim2 | n6,1ai100n\leq 6, 1\leq a_i \leq 100 | | 343\sim4 | n1000,1ai105n\leq 1000, 1\leq a_i\leq 10^5aia_i 互不相同 | | 565\sim6 | n100000,ain\leq 100000, a_i 互不相同 | | 787\sim8 | n100000,1ai105n\leq 100000, 1\leq a_i \leq10^5 | | 9109\sim 10 | n100000,109ai109n\leq 100000, -10^9 \leq a_i \leq 10^9 |