【题目来源】
洛谷：P4447 [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
【解题思路】
【算法标签】
《洛谷 P4447 分组》 #贪心# #二分# #队列# #安徽# #2018#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 全局变量：
// n: 学生数量
// a[100005]: 存储学生能力值
// mark: 记录当前创建的队伍数量
// ans: 存储最终结果（最少人数队伍的人数）
int n, a[100005], mark = 0, ans;// 队伍结构体：num-队伍人数，sl-队伍技能等级
struct team
{int num, sl;
} ts[100005];/*** 将学生插入合适的队伍* @param k 当前学生的能力值*/
void insert(int k)
{int find = 0, flag, tnum = 100005;// 查找是否有技能等级为k-1的队伍for (int i = 0; i < mark; i++){if (ts[i].sl == k - 1){// 选择人数最少的符合条件的队伍if (ts[i].num < tnum){flag = i;find = 1;tnum = ts[i].num;}}}if (find == 1){// 找到合适队伍，更新队伍信息ts[flag].sl = k;ts[flag].num++;}else{// 没有合适队伍，创建新队伍ts[mark].sl = k;ts[mark].num = 1;mark++;}
}int main()
{// 输入学生数量scanf("%d", &n);// 输入学生能力值for (int i = 0; i < n; i++){scanf("%d", &a[i]);}// 对学生能力值进行排序sort(a, a + n);// 将每个学生插入合适的队伍for (int i = 0; i < n; i++){insert(a[i]);}// 初始化结果为第一个队伍的人数ans = ts[0].num;// 遍历所有队伍，找出人数最少的队伍for (int i = 1; i < mark; i++){if (ts[i].num < ans){ans = ts[i].num;}}// 输出最少人数队伍的人数printf("%d", ans);return 0;
}
【运行结果】
7
4 5 2 3 -4 -3 -5
3