【贪心】P4447 [AHOI2018初中组] 分组

题意概括

给定 $n$ 个队员的实力值，需要将他们分成若干个小组。要求每个小组内的实力值必须是连续的整数，且同一个组内不能出现相同的实力值。每个队员都必须恰好分入一个小组。求在所有合法的分组方案中，人数最少的小组人数的最大值。

输入第一行是一个正整数 $n$；第二行包含 $n$ 个整数，代表队员的实力值。 数据范围：$1 \leq n \leq 10^5$，实力值的绝对值不超过 $10^9$。

保留样例

输入：

7
4 5 2 3 -4 -3 -5

输出：

3

解释：可以将这 7 个数字分成两组：[-5, -4, -3] 和 [2, 3, 4, 5]。两组内部都是连续且不重复的整数。两组的人数分别为 3 和 4，其中人数较少的是 3。没有更优的分法能让最少人数大于 3。

样例分析

拿到样例中的 7 个数字：4 5 2 3 -4 -3 -5。 如果把它们从小到大排个序，序列就变成了：-5, -4, -3, 2, 3, 4, 5。

顺着这个顺序看： 前面的 -5, -4, -3 是连在一起的，它们可以刚好组成一组，长度是 3。 接下来的 2 和前面断开了，它只能自己新开一组。后面的 3, 4, 5 可以顺次接在 2 后面，组成 [2, 3, 4, 5] 这一组，长度是 4。 此时所有的数字都分配完毕，一共分成了两组，人数较少的那一组人数就是 3。

题目分析

要让每个分组的实力值连续且不重复，处理这种具有连续性要求的问题时，将数据从小到大排序是一个自然的切入点。排序后，相近的、连续的数字就会排在一起。

排好序后可以按顺序处理每一个数字。对于当前的数字 $x$，有两种选择：把它接到某一个现有的、以 $x-1$ 结尾的小组后面；或者让它作为开头，自己新成立一个小组。

为了让最终“人数最少的小组人数最大”，在有多个现有小组都以 $x-1$ 结尾时，应该优先把 $x$ 接到当前人数最少的那一组后面。这是因为短板决定了最终的答案，把新数字分配给当前最短的小组，能最有效地拉长这个短板。如果没有以 $x-1$ 结尾的小组，说明现有的组都无法容纳 $x$，此时 $x$ 只能自己新开一组，初始人数为 1。

为了高效地实现这个挑选过程，需要记录每一个小组的结尾数值以及该小组的当前人数。可以使用一个映射，它的键是小组的结尾数值，对应的值是一个最小堆（优先队列）。最小堆里存放所有以该数值结尾的小组的人数。这样每次处理数字 $x$ 时，只需看 $x-1$ 对应的最小堆是否为空：

• 如果不为空，取出堆顶（也就是最短的小组人数），将其加 1 后放入 $x$ 对应的最小堆中。
• 如果为空，说明无法拼接，直接在 $x$ 对应的最小堆中插入 1。

把所有数字处理完后，遍历整个结构，找出所有现存小组人数的最小值即可。

参考实现

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int a[100005];
map<int, priority_queue<int, vector<int>, greater<int>>> mp;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    sort(a, a + n);
    
    for (int i = 0; i < n; i++) {
        int x = a[i];
        if (mp[x - 1].empty()) {
            mp[x].push(1);
        } else {
            int len = mp[x - 1].top();
            mp[x - 1].pop();
            mp[x].push(len + 1);
        }
    }
    
    int ans = 2e9;
    for (auto &p : mp) {
        if (!p.second.empty()) {
            ans = min(ans, p.second.top());
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}

复杂度分析

• 时间复杂度：排序需要 $O(n \log n)$ 的时间。随后的遍历中，对每个元素进行 Map 查找以及优先队列的插入与删除操作，单次操作时间复杂度为 $O(\log n)$。因此总时间复杂度为 $O(n \log n)$，可以稳定通过所有测试点。
• 空间复杂度：主要消耗在存储原始实力的数组以及 Map 和优先队列上，它们总共存储的元素数量不会超过 $O(n)$，空间复杂度为 $O(n)$。

https://www.luogu.com.cn/problem/P4447