目录
形式化题目
给定
- 每组内的数值互不相同；
- 每组内的数值排序后是连续整数（相邻两项恰好差
）。
在所有合法划分中，让人数最少的组尽可能大，输出这个最大值。
样例：
数值可能为负，组数不限。
解法路线
题面自带五档子任务，正好对应五步推进。每步都复用上一步的观察，只移除一个新的瓶颈：
| 层 | 做法 | 复杂度 | 覆盖 | 突破的瓶颈 |
|---|---|---|---|---|
| 1 | 枚举分组编号 | —— | ||
| 2 | 排序 + 逐元素接最短链 | 从枚举变成确定性构造 | ||
| 3 | 扫描连续段 | 利用互不相同，链数降为 1 | ||
| 4 | 桶 + 堆 | 允许重复，需堆管理多条链 | ||
| 终 | 分块 + 双堆 | 坐标压缩，容纳负数与 |
其中「2」到「4」是两次真正的思维跳跃；「3」是「2」在无争夺情形下的自然退化，本身不构成新跳跃。
正式主解是正解，代码在 main.cpp。
暴力解法
适用范围
思路
按定义直接枚举。方案就是一个「分组编号序列」：belong[i] 表示第
到叶子节点时统一检查合法性：把同组的数值收集起来排序，逐项检查「组内不重复」和「相邻差 1」。全部合法就用「人数最少的组的人数」更新答案。
组号本身没有标号意义，所以同一划分会被重复枚举（两人一组时组号可交换），但这只影响枚举次数，不影响
代码
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-06-20 13:47
* update_at: 2026-10-22 23:20
*/
// brute.cpp：小数据暴力解，使用「分组编号序列」递归枚举所有分法。
//
// 这一层枚举的是「第 dep 个队员分到第几个组」，每个位置有 n 种选择（组号 1..n），
// 共 n^n 种。到叶子节点时统一检查合法性：
// 1. 每组内数值互不相同；
// 2. 每组内数值排序后相邻恰好差 1（即连续）。
// 全部合法就用「人数最少的组的人数」去更新答案。
//
// 组号本身没有标号意义，所以同一个划分会被重复枚举（比如两人一组时组号可交换），
// 但这只影响枚举次数，不影响 max-min 的结果，暴力不必去重。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10;
int n;
int a[MAXN];
int belong[MAXN]; // belong[i] = 第 i 个队员被分到的组号（1..n）
int best_answer; // 所有合法方案中「最小组人数」的最大值
// 到叶子节点：belong[] 已给出完整分法，检查它是否合法并更新答案
void check() {
// 按组号收集每组的成员
vector<int> group[MAXN];
for (int i = 1; i <= n; i++) {
group[belong[i]].push_back(a[i]);
}
int min_size = n; // 本方案里人数最少的组的人数
for (int g = 1; g <= n; g++) {
if (group[g].empty()) continue;
sort(group[g].begin(), group[g].end());
// 条件一：组内不能有两个相同的实力值
for (int k = 1; k < (int)group[g].size(); k++) {
if (group[g][k] == group[g][k - 1]) return;
}
// 条件二：相邻两项必须恰好差 1（排序后连续）
for (int k = 1; k < (int)group[g].size(); k++) {
if (group[g][k] != group[g][k - 1] + 1) return;
}
min_size = min(min_size, (int)group[g].size());
}
best_answer = max(best_answer, min_size);
}
// 这一层在决定「第 dep 个队员分到第几组」
void dfs(int dep) {
if (dep > n) {
check();
return;
}
for (int g = 1; g <= n; g++) {
belong[dep] = g;
dfs(dep + 1);
}
belong[dep] = 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
best_answer = 0;
dfs(1);
cout << best_answer << '\n';
return 0;
}复杂度与瓶颈
时间
瓶颈是枚举的对象不对：它枚举了「每个队员进哪组」，而组本身是可以构造的。只要找到构造规则，就不需要枚举。
第一层：从枚举到确定性构造
适用范围
思路
能不能换个视角看「分组」这件事？
可以。把每个组看成一条链：链上的值依次加
这样就得到一条很强的事实：
值
的队员，只能接到当前以 结尾的链上；接不上就只能以 新开一条长度为 的链。
这条依赖关系把「全局划分」变成了「按值顺序的局部决策」——决策顺序被值域唯一确定，这是能贪心的前提。
多条链可接时，接哪一条？
接最短的。用交换论证：设某个最优解在这一步把
直觉上，长链已经「安全」，短链才是随时会被问到最小值的那条。
没被接上的链怎么办？
它们停在原地，长度永久定格。这一步不需要额外处理——没被选中的链自然留在原处，冻结是自动发生的。而答案正是最小链长，所以这些定格值会直接决定答案上界。
于是算法只有一条规则：排序后逐个队员处理，把他接到「以
代码
main2.cpp 忠实地按上述规则模拟：每次线性扫描所有链，找结尾值为
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-22 23:20
* update_at: 2026-10-22 23:20
*/
// main2.cpp：第二层解法，排序后逐元素模拟接链，O(n^2)。
//
// 层 1 枚举了所有分法但数量爆炸；能不能直接构造？
//
// 关键观察：把每个组看成一条「链」，链上的实力值依次加 1。
// 按实力值从小到大处理每个队员时，他只能接到「以 a_i - 1 结尾」的链上，
// 接不上就只能新开一条长度为 1 的链 —— 决策顺序被值域唯一确定。
//
// 有多条链可接时接哪条？接最短的。短链才是最可能成为「最小组」的那条，
// 把增长机会给它，最小值不会下降（交换论证）。这一条规则就是全部贪心：
// 没人被接的链自然停在原地，冻结这件事自动发生了，不需要额外处理。
//
// 实现上没有堆，每次线性扫描所有链找最短的可接链，所以是 O(n^2)。
// 能过 n <= 1000 的 3~4 号测试点；再往上要靠第三层的桶/堆优化。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n;
int a[MAXN];
struct Chain {
int end_value; // 这条链的最后一个实力值
int length; // 这条链当前的组人数
};
Chain chains[MAXN]; // 最多 n 条链，每条至少 1 人
int chain_cnt = 0;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
int value = a[i];
// 在所有链里找「能以 value-1 结尾接上」且长度最短的那一条
int pick = -1;
for (int c = 0; c < chain_cnt; c++) {
if (chains[c].end_value != value - 1) continue;
if (pick == -1 || chains[c].length < chains[pick].length) {
pick = c;
}
}
if (pick != -1) {
// 接到最短的链后面，链长加 1
chains[pick].end_value = value;
chains[pick].length++;
} else {
// 接不上任何链，只能新开一条长度 1 的链
chains[chain_cnt].end_value = value;
chains[chain_cnt].length = 1;
chain_cnt++;
}
}
// 所有队员处理完后，每条链的长度已经定型，取最小的那个
int answer = n;
for (int c = 0; c < chain_cnt; c++) {
answer = min(answer, chains[c].length);
}
cout << answer << '\n';
return 0;
}复杂度与瓶颈
每处理一个队员要扫描全部链，共
瓶颈是**「找最短的可接链」这一步扫了全部链**。但可接的链只由「结尾值是否等于
第二层：互不相同时，选择规则消失
适用范围
思路
第一层无论何时都要处理「多条链可接时接哪条」，因为同一个结尾值可能挂着好几条链。
但互不相同意味着每个实力值最多只有一个队员，于是「以某值结尾的链」最多只有一条——争夺消失了，「接最短」这条选择规则也就消失了。
剩下的问题变成：每个队员只问一句「以我结尾的那条链有多长？」
这是一层链长 DP，找前驱直接线性扫描，所以仍是
两个实现细节必须注意：
- 必须先排序。DP 递推要求「前驱的链长已经算好」，而
只有排在 之前才满足。若按输入原序递推，会出现「需要的前驱还没算」的情况——例如 4 5 2 3 -4 -3 -5中，4的前驱3排在它后面，此时len还是初始值。 - 答案只能在链终点收集。中间点的
len是前缀长度而不是组大小，若把它也算进最小值会得到偏小的错误答案。所以要标记哪些点还有后继（存在），只在没有后继的终点上取最小值。
代码
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-22 23:55
* update_at: 2026-10-22 23:55
*/
// main2-1.cpp：第二层的「互不相同」特化解，套一层链长 DP，O(n^2)。
// 本层针对 3~4 号测试点：n <= 1000，且 a_i 互不相同。
//
// 与 main2.cpp 的区别：main2.cpp 无论如何都要处理「多条链可接时接哪条」，
// 因为同一个结尾值可能挂着好几条链。但 3~4 保证 a_i 互不相同，
// 每个实力值最多只有一个队员，于是「以某值结尾的链」最多只有一条 ——
// 争夺消失了，「接最短」这条选择规则也就消失了。
//
// 剩下的问题变成：每个队员只问「以我结尾的那条链有多长？」
// 若 a_i - 1 这个值不存在，我就是一条新链的起点，长度为 1；
// 若存在，我就接在它后面，长度是它的链长加 1。
// 这就是一层链长 DP：
//
// len[i] = 1 , 若不存在 j 使 a[j] == a[i] - 1
// len[i] = len[j] + 1 , 否则（那个 j 唯一）
//
// 找前驱 j 直接线性扫描，所以是 O(n^2)。
//
// ⚠ 必须先把 a[] 排序。这一层 DP 的递推要求「前驱的链长已经算好」，
// 而 a_i - 1 只有排在 a_i 之前才能保证这一点。若按输入原序递推，
// 会出现「需要的前驱还没算」的情况（例如 4 5 2 3 -4 -3 -5 中，
// 4 的前驱 3 排在它后面，此时 len 还是初始值），答案就错了。
//
// ⚠ 答案只能在「链的终点」上收集。中间点的 len 只是前缀长度，
// 若把它也算进去会得到偏小的错误答案；只有没有后继（a_i + 1 不存在）的点
// 才携带完整组大小。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n;
int a[MAXN];
int len[MAXN]; // len[i] = 以 a[i] 结尾的链的长度（a[i] 是链的最后一个值）
bool has_next[MAXN]; // has_next[i] = 是否存在 a[j] == a[i] + 1，即 i 不是链的终点
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
// 排序：让 a_i - 1 一定排在 a_i 之前，DP 递推才有意义
sort(a + 1, a + n + 1);
// 互不相同是本层前提，检查一遍：本层若遇到重复值会给出错误答案
// （同一个值出现两次时，「以某值结尾的链只有一条」不再成立）
for (int i = 2; i <= n; i++) {
if (a[i] == a[i - 1]) {
cerr << "[main2-1] 本层只适用于 a_i 互不相同的 3~4 号测试点，"
<< "但读到了重复的实力值 " << a[i]
<< "；请改用 main.cpp（分块 + 双堆）\n";
return 1;
}
}
// 第一步：线性扫描求每个点的前驱，得到链长
for (int i = 1; i <= n; i++) {
len[i] = 1; // 默认自己是链的起点
for (int j = 1; j <= n; j++) {
if (a[j] == a[i] - 1) {
// 找到了唯一的前驱，接在它后面
len[i] = len[j] + 1;
break;
}
}
}
// 第二步：标记哪些点还有后继。没有后继的点才是链的终点，
// 只有终点的 len 是完整组大小；中间点的 len 只是前缀长度。
for (int i = 1; i <= n; i++) {
has_next[i] = false;
for (int j = 1; j <= n; j++) {
if (a[j] == a[i] + 1) {
has_next[i] = true;
break;
}
}
}
// 答案 = 所有链终点上的 len 的最小值
int answer = n;
for (int i = 1; i <= n; i++) {
if (!has_next[i]) {
answer = min(answer, len[i]);
}
}
cout << answer << '\n';
return 0;
}复杂度与瓶颈
仍为
瓶颈仍在「找前驱要扫描全部元素」。
第三层：连续段整体成组
适用范围
思路
既然没有两个队员实力值相同，就不会有两个人争抢同一条链的位置。那么排序后，数组自动被切成若干段「连续区间」，区间之间差至少
**每段连续区间整体就是一组。**两个理由：
- 段内数值连续且互不相同，天然满足「连续」和「不重复」，可以直接作为一组；
- 若把它切成更小的组，只可能让最小的组更小，不会让答案变大。
所以最优方案就是「每段连续区间各成一组」，扫一遍取最短的那一段。
注意是取最短而不是最长：题目要最大化最小组人数，而最短的连续段已经决定了上限。例如
这一层与前一层的联系：从「链」的视角看，互不相同时每个值最多一条链，链与链之间没有交互，于是最优策略必然是「一条链顶到不能再顶」——也就是把整段连续区间吃满。DP 在这里退化成了一次扫描。
代码
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-22 23:45
* update_at: 2026-10-22 23:45
*/
// main3.cpp：第三层解法，扫描连续段，O(n log n)。
// 本层针对 5~6 号测试点：n <= 1e5，但 a_i 互不相同。
//
// 关键观察：既然没有两个队员实力值相同，就不会有两个人争抢同一条链的位置。
// 于是把 a[] 排序后，它自动被切成若干段「连续区间」，区间之间差至少 2。
//
// 为什么每段连续区间整体就是一组？
// - 段内数值连续且互不相同，天然满足「连续」和「不重复」，可以直接作为一组；
// - 若把它切成更小的组，只可能让最小的组更小，不会让答案变大。
// 所以最优方案就是「每段连续区间各成一组」，答案取这些段里最短的那一段。
//
// 注意是取「最短」而不是「最长」：题目要最大化最小组人数，而最短的连续段
// 已经决定了上限，段内再细切只会更差。例如 [1,2,10,11,12] 分成 2 组，
// 最短段长 2，答案就是 2，而不是最长段的 3。
//
// 与第四层的关系：本层其实是第四层在无重复情形下的退化 —— 每个值的桶里
// 最多只有一个元素，堆退化成普通栈，于是不需要堆，扫一遍连续段即可。
// 值一旦允许重复（7~8 号点），就必须用桶 + 堆，见 main4.cpp。
//
// ⚠ 本层直接用「整段作为一组」，一旦存在重复值就会给出错误答案
// （例如 {-1,0,0,1,1,2,3} 正确是 3，本层会算成 2）。所以读入后先检查
// 是否有重复，有则提示改用 main4.cpp，避免静默返回错解。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n;
int a[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
// 本层的前提是「实力值互不相同」，检查一遍，不满足就明确提示
for (int i = 2; i <= n; i++) {
if (a[i] == a[i - 1]) {
cerr << "[main3] 本层只适用于 a_i 互不相同的 5~6 号测试点，"
<< "但读到了重复的实力值 " << a[i]
<< "；请改用 main4.cpp（桶 + 堆）\n";
return 1;
}
}
// 扫描排序后的数组，找每一段满足 a[j+1] == a[j] + 1 的连续区间
int answer = n; // 最小组人数，先取最坏上界
int left = 1;
while (left <= n) {
int right = left;
while (right + 1 <= n && a[right + 1] == a[right] + 1) {
right++;
}
// 区间 [left, right] 就是一组，人数是 right - left + 1
answer = min(answer, right - left + 1);
left = right + 1;
}
cout << answer << '\n';
return 0;
}复杂度与瓶颈
排序
瓶颈变成**「互不相同」这个前提本身**。一旦允许重复，同一段连续区间里会出现「人多位置少」的情况，就必须切成多条链——「整段成组」不再成立。
正解
关键观察
值
：旧链全部接上，多出的 个队员新开长度为 的链； ：一一对接，不新开； ：必须有 条链接不上而冻结，它们停在 不再增长。
第三种是重复值带来的新情况，也是前一层的「整段成组」失效的地方。链一旦断掉长度就永久定格，而答案正是最小链长，所以冻结会直接决定答案上界。
必须冻结时，冻哪一条？冻最长的。
这是「接最短」的对偶：冻结是不可逆的惩罚，应当让最长的链去承受——它本来就大，冻住也不致命；反过来若冻最短，等于亲手制造一条很短的定格链。
两条规则方向相反但道理同源：把继续增长的机会给最需要的（最短的），把冻结的惩罚给最不痛的（最长的）。
思路
bucket[v]= 所有以实力值结尾的链长度，用小根堆维护。
处理值 bucket[x-1]：非空就弹出堆顶（堆顶就是最短链，「接最短」免费实现），接上后把长度加 bucket[x]；为空就新开一条长度
「没被接上的链自动冻结」在这里同样自动成立：取不完的链留在原桶里不再参与延长，而桶的键是结尾值，值推进后那些桶再也不会被访问，长度自然定型。
分桶的两种做法：
main4.cpp直接把当数组下标，最简单，但只能装下 （ 号点）； main.cpp用「排序后按值分块」代替定长数组，等效于坐标压缩，负数与都能装，且没有 map的额外常数。
正式主解用后者。
两个实现细节：
- 断档冻结必须排在延长之前。
cur里的链属于「以结尾」，断档时这个前提不成立，它们根本不该参与本轮延长。若把断档判断挪到最后， cur已被错误地接上——例如输入，正确答案是 （两条链 与 ），挪序后会得到 。 - 必须排序。规则「接以
结尾的链」只在值从小到大推进时成立。漏掉排序会先给大值建链、再回头处理小值，接续关系全错。
代码
main4.cpp 是值域受限（
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-22 23:20
* update_at: 2026-10-22 23:20
*/
// main4.cpp：第四层解法，按值域开桶 + 每个值一个堆，O(n log n)。
// 本层针对 7~8 号测试点：1 <= a_i <= 1e5，值域小，可以直接用值当下标。
//
// 层 2 的瓶颈在哪？它每个队员都要线性扫描所有链找最短的可接链，O(n^2)。
// 但「可接的链」只取决于一个东西：这条链是否以 value-1 结尾。于是按结尾值分桶：
//
// bucket[v] = 所有以实力值 v 结尾的链，用一个小根堆存它们的长度。
//
// 处理实力值 value 的队员时，只需要看 bucket[value-1]：非空就弹出堆顶
// （堆顶就是最短的那条，规则「接最短」免费实现），接上后把长度加 1 放进
// bucket[value]；为空就新开一条长度 1 的链放进 bucket[value]。
//
// 层 2 里那些「没被接上的链自动冻结」在这里同样自动成立：
// 队员只会从 bucket[value-1] 里取，取不完的链留在原桶里不再参与延长，
// 而桶的键是结尾值，value 推进后那些桶再也不会被访问，长度自然定型。
//
// ⚠ 必须先把 a[] 排序再按这个顺序处理。规则「接最短链」只在「值从小到大」
// 的推进顺序下成立；若按输入原序处理，会先给大值建链、再回头处理小值，
// 链的接续关系就错了（例如 3 2 2 3 1 3 2 1 按原序算得 1，排序后才是 2）。
//
// ⚠ 本层把 a_i 直接当桶下标，所以只对 7~8 号测试点的值域成立（1 <= a_i <= 1e5）。
// 数据里一旦出现 a_i <= 0 或 a_i > 1e5，下标就飞出数组 —— 下面在读入时直接拦住
// 并给出明确提示，而不是让它静默越界。一般值域请用 main.cpp 的坐标压缩版本。
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 100005; // 值域上限 1e5，桶开到这个大小多留一点余量
const int MAXA = 100000; // 7~8 号点保证 a_i <= 1e5
int n;
int a[MAXV];
// 每个实力值配一个小根堆，存「以它为结尾」的各条链长度
priority_queue<int, vector<int>, greater<int> > bucket[MAXV];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
// 本层用 a_i 直接做下标，越界就是数组越界，先拦住并说明原因
if (a[i] < 1 || a[i] > MAXA) {
cerr << "[main4] 本层只适用于 1 <= a_i <= " << MAXA
<< " 的 7~8 号测试点，但读到了 a_i = " << a[i]
<< "；请改用 main.cpp（坐标压缩版）\n";
return 1;
}
}
// 必须按实力值从小到大处理，规则「接最短链」才有意义
sort(a + 1, a + n + 1);
int answer = n; // 链长的最小值即答案，先取最坏上界
for (int i = 1; i <= n; i++) {
int value = a[i];
if (value >= 1 && !bucket[value - 1].empty()) {
// 有链以 value-1 结尾，接最短的那条（堆顶）
int len = bucket[value - 1].top() + 1;
bucket[value - 1].pop();
bucket[value].push(len);
} else {
// 没有可接的链，以 value 新开一条长度 1 的链
bucket[value].push(1);
}
}
// 扫一遍所有桶，取最小的链长
for (int v = 0; v < MAXV; v++) {
while (!bucket[v].empty()) {
answer = min(answer, bucket[v].top());
bucket[v].pop();
}
}
cout << answer << '\n';
return 0;
}main.cpp 是正式主解，用「排序 + 按值分块」实现分桶，用 cur / nxt 两个堆轮换：处理值 cur 是「以 nxt；每轮结束 swap 一次，nxt 在 swap 后为空可直接复用。
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-06-20 13:47
* update_at: 2026-10-22 22:55
*/
// P4447 [AHOI2018初中组] 分组
//
// 把每个组看成一条「链」：链上的实力值依次加 1，不跳也不重复。
// 于是「分组」等价于「把每个实力值的队员分配到若干条链上」。
//
// 按实力值从小到大处理，因为值 x 的队员只能接到「以 x-1 结尾」的链上，
// 接不上就只能以 x 新开一条长度为 1 的链。决策顺序被值域唯一确定，可以贪心。
//
// 三条规则，按执行顺序编号（前两条用交换论证证明不会让答案变差）：
// 一、实力值不连续时，前一段的链全部冻结，必须当场结算
// 二、有多条链可接时，接最短的 —— 短链最可能成为答案，优先给它增长机会
// 三、链比人多的部分接不上，只能冻结；冻结的应当是其中最长的那些
//
// 规则一必须先于规则二：cur 里的链属于「以 value-1 结尾」，断档时这个前提
// 不成立，它们根本不该参与本轮延长；若挪到后面，cur 已被规则二错误地接上。
// 规则一与规则三冻结链的动作完全一样，都归结为下面的 freeze_all()。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
typedef priority_queue<int, vector<int>, greater<int> > MinHeap;
int n;
int a[MAXN];
// 冻结堆里所有链：长度已定格，拿去更新答案后清空。
// 规则一（断档时冻掉整段）和规则三（冻掉接不上的最长链）都调用它。
void freeze_all(MinHeap &heap, int &answer) {
while (!heap.empty()) {
answer = min(answer, heap.top());
heap.pop();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
// 排序后扫描一遍，把相等的实力值压成一块：
// blocks[k].first = 这个实力值
// blocks[k].second = 拥有这个实力值的人数
// 这样后面按值块处理时，块的先后顺序就是实力值从小到大的顺序。
vector<pair<int, int> > blocks;
for (int i = 1; i <= n; ) {
int j = i;
while (j <= n && a[j] == a[i]) j++;
blocks.push_back(make_pair(a[i], j - i));
i = j;
}
// cur：以「当前值块的实力值」结尾的各条链长度，小根堆让最短的链先被取出。
// nxt：以「下一个值块的实力值」结尾的链。两者轮换，nxt 每次用完即空。
MinHeap cur, nxt;
int answer = n; // 链长的最小值即答案，先取最坏上界
// 上一块处理过的实力值。a_i 最小到 -1e9，用 long long 避免 value-1 溢出。
long long last_value = LLONG_MIN;
for (auto [value, count] : blocks) {
// ── 规则一（断档冻结）────────────────────────────────
// 与上一块不连续，cur 里的链无法再从 value-1 延续，整段冻结。
// 这一步必须先于规则二：否则这些链会被错误地接到 value 上。
// last_value 记录上一块的实力值，初值取一个不可能相邻的数。
if (value != last_value + 1) {
freeze_all(cur, answer);
}
last_value = value;
// ── 规则二（延长最短链）──────────────────────────────
// 能接的链里优先接最短的，所以从堆顶取。最多接 min(count, cur.size()) 条。
int extend = min(count, (int)cur.size());
for (int k = 0; k < extend; k++) {
nxt.push(cur.top() + 1);
cur.pop();
}
// ── 规则三（冻结最长链）──────────────────────────────
// 链比人多的那些接不上，只能停在上一块的值。刚才取走的是最短的若干条，
// cur 里剩下的正是最长的那些，全部冻结即「冻最长、保最短」。
freeze_all(cur, answer);
// 接不上旧链的队员，只能以当前值新开一条长度为 1 的链
for (int k = 0; k < count - extend; k++) {
nxt.push(1);
}
swap(cur, nxt); // nxt 在 swap 后为空，下一轮直接复用
}
// 收尾：最后一个值块留下的链全部冻结
freeze_all(cur, answer);
cout << answer << '\n';
return 0;
}Python 版用 defaultdict(list) 给每个结尾值配一个小根堆，逐个人处理即可，不必像 C++ 那样按值分块——因为同一个值的两个人不可能接到同一条链上（链内不可重复），所以逐个处理与分块处理等价。
python
"""P4447 [AHOI2018初中组] 分组
把每个组看成一条「链」：链上的实力值依次加 1，不跳也不重复。
于是「分组」等价于「把每个实力值的队员分配到若干条链上」。
按实力值从小到大处理，因为值 x 的队员只能接到「以 x-1 结尾」的链上，
接不上就只能以 x 新开一条长度为 1 的链。决策顺序被值域唯一确定，可以贪心。
三条规则，按执行顺序编号（前两条用交换论证证明不会让答案变差）：
一、实力值不连续时，前一段的链全部冻结，必须当场结算
二、有多条链可接时，接最短的 —— 短链最可能成为答案，优先给它增长机会
三、链比人多的部分接不上，只能冻结；冻结的应当是其中最长的那些
实现上用 defaultdict(list) 给每个「结尾实力值」配一个小根堆存链长：
堆顶总是以该值结尾的最短链，天然满足规则二（先取最短）
和规则三（剩下的都更长，冻结它们）。
规则一在逐个处理时自然消解：值 x-1 的堆为空即说明断档，不必显式判断。
"""
from collections import defaultdict
import heapq
import sys
def main() -> None:
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
abilities = data[1:1 + n]
abilities.sort()
# chains[v] = 以实力值 v 结尾的所有链长，小根堆维护，堆顶是最短的那条
chains = defaultdict(list)
# 链长的最小值就是答案，先取最坏上界 n
answer = n
for x in abilities:
if chains[x - 1]:
# 规则一：能接就接最短的（堆顶），长度加 1 后挂到 x 这端
length = heapq.heappop(chains[x - 1]) + 1
else:
# 接不上任何旧链，只能以 x 新开一条长度为 1 的链
length = 1
heapq.heappush(chains[x], length)
# 所有值的队员都安排完了，堆里剩下的每条链长度都已定格，
# 逐个取最小值即为答案。
# 注意：同一实力值不会出现在两个不同的 x 上，所以每个链只被统计一次。
for heap in chains.values():
for length in heap:
if length < answer:
answer = length
print(answer)
if __name__ == "__main__":
main()复杂度
注意一条链会被反复取出、放入，所以不能按「每条链一次」来数堆操作；正确做法是分别数 push 与 pop 的总次数。
**push 次数恒为 extend 次加上新开的 count - extend 次正好是 count，而各值块互不重叠、并起来就是全部
**pop 次数也恒为 while (!cur.empty()) 再弹出所有遗留元素，于是每个元素恰好被 pop 一次。
所以堆操作总次数是
实测 main3.cpp 在互不相同数据上约
总结
五层推进，每层只做一件事：
| 层 | 关键动作 |
|---|---|
| 暴力 | 把「合法划分」写成可检验的判据 |
| 一 | 看穿「组 = 连续链」，决策顺序被值域确定 |
| 二 | 互不相同时争夺消失，选择规则可以删掉 |
| 三 | 无争夺时链与链无交互，最优必是「整段吃满」 |
| 正解 | 有争夺时按结尾值分桶，用堆在多条链间做取舍 |
真正有教学价值的是两次跳跃：
- 枚举 → 构造：观察「值
只能接 的链」，全局划分塌缩成按值顺序的局部决策； - 逐元素 → 按值聚合：可接的链只取决于结尾值，所以分桶；桶内多条链的取舍交给堆。
第三层不是新的跳跃，而是第二层在「无争夺」下的自然退化——它的价值是让人看清堆为什么必要：每个值只有一个元素时，堆退化成栈，扫一遍就够；一旦有重复，堆才真正开始工作。
两条易错点，都实测过：
- 把「冻最长」错写成「冻最短」：3000 组随机数据里会有 435 组答案出错；
- 执行次序颠倒（断档冻结挪到延长之后）：输入
会从正确的 变成 。
一个边界要说明：这套规则依赖目标是最大化最小值。若目标改成最小化最大值（即不让某组过长），规则就要反向。所以它不是「分组问题」的通用规律，而是这个目标函数专属的。