「ACM 算法实践」[解题报告]组队

分析

因为时间不多了，我一开始只考虑了 \(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;
}