P4447 [AHOI2018初中组]分组

    • 413通过
    • 1.3K提交
  • 题目提供者 yyy2015c01 嘤嘤嘤
  • 评测方式 云端评测
  • 标签 二分答案 期望 贪心 队列 2018 安徽
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

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

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

    输入输出格式

    输入格式:

    输入有两行:

    第一行一个正整数n,表示队员数量。
    第二行有n 个整数,第i 个整数a[i]表示第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$,$|a[i]|≤10^9$。

    本题共10 个测试点,编号为1~10,每个测试点额外保证如下:

    1~2 $n≤6, 1≤a[i]≤100$
    3~4 $n≤1000, 1≤a[i]≤10^5$ 且a[i]互不相同
    5~6 $n≤100000, a[i]$互不相同
    7~8 $n≤100000, 1≤a[i]≤10^5$
    9~10 $n≤100000, |a[i]|≤10^9$

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。