排序后把每个人接到以前一实力值结尾的最短链上，否则新开一组，最后取所有链长最小值。
OJ: luogu
题目 ID: P4447
难度:普及+/提高
标签:贪心堆思维python
日期: 2026-06-20 13:47
题意
给出 n 个队员的实力值，要把所有人分成若干组。每组内实力值必须连续，且不能有重复实力值。求一种分组方案，使最小组人数尽可能大，并输出这个最大值。
思路
先看一个小数据暴力：
cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
int n;
int a[MAXN];
map<int, int> cnt;
int best_answer;
void dfs(map<int, int> current_cnt, int current_min_len, bool has_group) {
bool empty = true;
int start = 0;
for (map<int, int>::iterator it = current_cnt.begin(); it != current_cnt.end(); ++it) {
if (it->second > 0) {
empty = false;
start = it->first;
break;
}
}
if (empty) {
if (has_group) {
best_answer = max(best_answer, current_min_len);
}
return;
}
vector<int> group;
int x = start;
while (current_cnt[x] > 0) {
current_cnt[x]--;
group.push_back(x);
int next_min = has_group ? min(current_min_len, (int)group.size()) : (int)group.size();
dfs(current_cnt, next_min, true);
x++;
}
for (int i = 0; i < (int)group.size(); i++) {
current_cnt[group[i]]++;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
cnt[a[i]]++;
}
best_answer = 0;
dfs(cnt, n, false);
cout << best_answer << '\n';
return 0;
}正解把每个组看成一条连续链。按实力值从小到大处理每个人：
- 如果存在以前一实力值
x-1结尾的链，就把当前x接到其中一条链后面； - 如果不存在，只能用
x新开一条长度为1的链。
关键是：有多条链都能接时，应该接到最短的那条链上。因为题目关心最小组长度，短链最危险，优先延长短链不会让答案变差。
因此用 chains[v] 维护“以实力值 v 结尾的所有链长”，并用小根堆让最短链优先弹出。
处理 x 时：
- 若
chains[x-1]非空，弹出最短链长len，把len+1放进chains[x]； - 否则，把一条长度为
1的新链放进chains[x]； - 所有人处理完后，所有堆里的最小链长就是答案。
Python 知识
defaultdict(list)可以为每个结尾实力值自动准备一个链长堆。heapq.heappop取出当前可延长的最短链。- 排序后逐个处理相同实力值也没问题，因为同一条链不能接两个相同值，只能从
x-1转移到x。
代码
python
from collections import defaultdict
import heapq
import sys
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
abilities = data[1:1 + n]
abilities.sort()
chains = defaultdict(list)
answer = n
for x in abilities:
if chains[x - 1]:
length = heapq.heappop(chains[x - 1]) + 1
else:
length = 1
heapq.heappush(chains[x], length)
for heap in chains.values():
for length in heap:
if length < answer:
answer = length
print(answer)
if __name__ == "__main__":
main()复杂度
排序复杂度是
空间复杂度是
总结
这题的关键是把分组看成连续链，并且“优先拯救短链”。Python 用字典加小根堆可以直接表达这个贪心。
一图流解析
这张图把本题的建模和贪心取舍压缩到一页，适合读完正文后复盘。
