分析
因为时间不多了，我一开始只考虑了 \(a_i\) 互不相等的情况，没想到居然拿到了 60 昏（
正确解法是贪心 + 优先队列。而不是从「使得人数最少的队伍人数最多」中得到的二分
首先肯定要将 a 数组排序，要使人数最少的队伍人数最多，我们优先将当前的数 \(a[i]\) 放到以 \(a[i]-1\) 结尾的队伍中人数最少的一个队伍即可。思路很简单，这题的难点在于怎么实现。
如果用一个 queue 来储存当前已经有了的队伍，然后再暴力查找符合要求的人数最少的队伍，时间复杂度 \(\mathcal{O}(n^2)\) ，肯定会 T ，于是我们考虑用优先队列来存储每条队伍的人数，查找时只需输出队头即可，这时候又如何存储每条队伍最后一个元素呢？可以开 n 条优先队列，q[i] 表示以 a[i] 结尾的所有队伍的人数，同时我们还需要对 a[i] 进行离散化，这样一来，分别为每一个人分队是 \(\mathcal{O}(n)\) 的，priority_queue 的操作是 \(\mathcal{O}(n\log{n})\) 的，所以 总复杂度是 \(\mathcal{O}(n\log{n})\) 。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <unordered_map>
#include <algorithm>
#define DEBUG puts("ok")
using namespace std;
int gi() {
char c = getchar(); int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
const int N = 1e5 + 5;
int n, m, ans;
int a[N], b[N], cnt[N];
priority_queue <int, vector<int>, greater<int> > q[N];
int main() {
n = gi();
for (int i = 1; i <= n; ++i) a[i] = gi(), b[i] = a[i];
sort(a + 1, a + 1 + n), sort(b + 1, b + 1 + n);
m = unique(b + 1, b + 1 + n) - b - 1;
int k = 1;
for (int i = 1; i <= m; ++i)
while (a[k] == b[i]) cnt[i]++, k++;
for (int i = 1; i <= cnt[1]; ++i) q[1].push(1);
for (int i = 2; i <= m; ++i) {
if (b[i] == b[i - 1] + 1) {
while (q[i - 1].size() && cnt[i]) {
q[i].push(q[i - 1].top() + 1);
q[i - 1].pop();
cnt[i]--;
}
if (cnt[i]) {
while (cnt[i])
q[i].push(1), cnt[i]--;
}
}
else {
while (cnt[i])
q[i].push(1), cnt[i]--;
}
}
ans = n;
for (int i = 1; i <= m; ++i)
if (q[i].size()) ans = min(ans, q[i].top());
printf("%d", ans);
return 0;
}