[AHOI2018初中组] 分组（洛谷P4447）
题目描述
小可可的学校信息组总共有 \(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
样例输入 #1
7
4 5 2 3 -4 -3 -5
样例输出 #1
3
提示
【样例解释】
分为 \(2\) 组，一组的队员实力值是 \(\{4, 5, 2, 3\}\)，一组是 \(\{-4, -3, -5\}\)，其中最小的组人数为 \(3\)，可以发现没有比 \(3\) 更优的分法了。
【数据范围】
对于 \(100\%\) 的数据满足：\(1\leq n\leq 100000\)，\(|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 100000, a_i\) 互不相同 |
| \(7\sim8\) | \(n\leq 100000, 1\leq a_i \leq10^5\) |
| \(9\sim 10\) | \(n\leq 100000, -10^9 \leq a_i \leq 10^9\) |
解答
- 利用二分及其单调队列的优化思想
- 将所有数进行排序，然后枚举每个数
- 看当前数加到哪个集合里，集合定义为
q[i]，存的是当前集合中数的最大值 - 二分找到第一个小于
a[i]的数，如果等于a[i] - 1，那么将这个数加到集合里，并且这个集合长度++ - 如果不等于，新创个集合，这个数加到这里面，长度赋值为
1，最大值为当前数 - 我还犹豫后面比他小的数也想加到这个集合呢，显然不可能，这就是先把其排序的奥妙，当前数不能加到前面集合，就只能创个集合
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N], siz[N], q[N];
int n;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a + 1, a + n + 1);
q[0] = 1e9;
int len = 0;
for (int i = 1; i <= n; i++)
{
int l = 0, r = len;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (q[mid] <= a[i]) l = mid;
else r = mid - 1;
}
if (q[l] != a[i]) siz[++len] = 1, q[len] = a[i] + 1;
else siz[l]++, q[l]++;
}
int ans = 1e9;
for (int i = 1; i <= len; i++)
ans = min(ans, siz[i]);
printf("%d\n", ans);
return 0;
}