第 5 章排序、贪心与构造#

本章目标：理解排序如何暴露结构，掌握贪心算法的证明方法，并学会从不变量出发构造答案。

5.1 学习目标#

掌握常见排序算法的复杂度和稳定性。
能设计正确的比较器。
理解贪心的局部最优与全局最优。
掌握交换论证、反证法和不变量证明。
学会构造题的常见突破口。

5.2 排序的意义#

排序不是为了“排好看”，而是为了让关系变简单。

排序后常出现：

相邻元素关系。
前缀最优或后缀最优。
单调性。
可用双指针。
可用贪心选择。

例如区间合并：按左端点排序后，只需比较当前区间和最后一个合并区间。

5.3 排序算法对比#

算法	平均复杂度	最坏复杂度	稳定性	备注
冒泡排序	$O(n^2)$	$O(n^2)$	稳定	教学用
插入排序	$O(n^2)$	$O(n^2)$	稳定	小数组快
归并排序	$O(n\log n)$	$O(n\log n)$	稳定	需要额外空间
快速排序	$O(n\log n)$	$O(n^2)$	不稳定	常数小
堆排序	$O(n\log n)$	$O(n\log n)$	不稳定	原地
计数排序	$O(n+V)$	$O(n+V)$	可稳定	值域小

5.4 比较器的严格弱序#

自定义排序比较器必须满足：

反自反：comp(x,x) 为 false。
传递性：若 x < y 且 y < z，则 x < z。
等价类传递。

错误示例：

1
sort(a.begin(), a.end(), [](int x, int y) {
2
    return x <= y;  // 错误：x == y 时也返回 true
3
});

正确写法：

1
return x < y;

5.5 贪心算法#

贪心每一步做当前看起来最好的选择。但“看起来最好”不代表真的对。

贪心要证明：

贪心选择性质：存在一个最优解包含当前选择。
最优子结构：做出选择后，剩余问题仍是同类最优问题。

5.6 交换论证#

例：活动选择问题。给定若干区间，选择最多互不重叠区间。

贪心：每次选结束时间最早的区间。

证明：设最优解中第一个选择为 A，贪心选择为 G。由于 G 的结束时间不晚于 A，用 G 替换 A 不会减少后续可选区间数量。因此存在一个包含 G 的最优解。

这说明贪心第一步安全，后续递归同理。

5.7 常见贪心模型#

5.7.1 区间调度#

按结束时间排序。
能选就选。
目标是数量最多。

5.7.2 区间覆盖#

按左端点排序。
在所有能接上的区间中选右端点最远的。
目标是用最少区间覆盖目标区间。

5.7.3 Huffman 合并#

每次合并最小的两个权值。

总成本：

\sum \text{merge cost}

用小根堆实现，复杂度 $O(n\log n)$ 。

5.8 构造题#

构造题要求输出一个满足条件的对象，而不是最优值。

常见突破口：

奇偶性。
模运算余数。
排列位置。
图的度数。
不变量。
从小规模样例找规律。

构造题的关键是保证每一步都不破坏条件。

5.9 易错点#

贪心没有证明，只靠直觉。
排序比较器写成非严格关系。
区间开闭端点处理不一致。
Huffman 合并忘记用 long long。
构造题只考虑样例，没有覆盖小规模所有情况。
忘记证明构造结果一定存在或说明无解条件。

5.10 练习#

证明活动选择的贪心正确性。
实现区间合并和区间覆盖。
用堆实现 Huffman 合并成本。
找一个贪心失败的反例，并解释为什么失败。
构造一个长度为 n 的排列，使相邻差满足指定条件。

ACM/OI 扩展：贪心证明与构造套路#

本节补充 OIer 和 ACMer 常用的算法套路、模板、复杂度分析和易错点。写模板时默认使用 C++17，变量名尽量短，但注释要说明不变量和适用条件。

1. 排序后贪心通用证明#

很多贪心题先排序，再做局部选择。题解要写清排序依据。

\text{若交换 } a,b \text{ 前后总代价比较为 } C_{ab} \le C_{ba}, \text{ 则 } a \text{ 应在 } b \text{ 前。}

要点：

若按结束时间排序，通常为了给后续留更多空间。
若按差值排序，通常来自交换相邻元素的收益比较。
若按比值排序，要注意交叉相乘避免浮点误差。

2. 区间覆盖模板#

用最少区间覆盖目标 [L,R]。

1
sort(seg.begin(), seg.end());
2
int i = 0, ans = 0;
3
while (L < R) {
4
    int far = L;
5
    while (i < n && seg[i].l <= L) {
6
        far = max(far, seg[i].r);
7
        ++i;
8
    }
9
    if (far == L) { ans = -1; break; }
10
    L = far; ++ans;
11
}

要点：

每次在能接上的区间中选右端点最远。
排序按左端点升序。

常见坑：

闭区间和半开区间要统一。

3. 差值排序模型#

两种选择 A/B，每个对象放一边，常按贡献差排序。

\Delta_i = costA_i - costB_i

要点：

如果必须选 k 个放 A，通常选 $\Delta_i$ 最小的 k 个。
如果目标是最大收益，则按收益差反向排序。

4. 构造题常用不变量#

构造题应先找必须保持的性质。

要点：

奇偶性：总和奇偶、位置奇偶、颜色奇偶。
模数：按余数分组构造。
图论度数：度数和必须为偶数。
排列：从小规模 n=1..8 暴力找规律。
贪心补位：每一步选择不破坏剩余可行性。

训练题型：

构造一个排列使相邻和不为质数。
构造括号序列满足前缀和非负。

5. Huffman 合并模板#

每次合并最小两项，常见于最优合并代价。

1
priority_queue<long long, vector<long long>, greater<long long>> pq;
2
for (auto x : a) pq.push(x);
3
long long ans = 0;
4
while (pq.size() > 1) {
5
    long long x = pq.top(); pq.pop();
6
    long long y = pq.top(); pq.pop();
7
    ans += x + y;
8
    pq.push(x + y);
9
}

要点：

复杂度 $O(n\log n)$ 。
权值和可能超过 int。

本章模板背诵清单#

能在 5 分钟内写出本章第一个核心模板。
能说出每个模板的时间复杂度和空间复杂度。
能说明模板不适用的反例。
能为模板构造 3 个边界样例。
能把模板改成 0-index 或 1-index 版本。

构造与贪心题库套路#

邻项交换法#

排序规则常通过比较 AB 和 BA 两种相邻顺序得到。

A \text{ before } B \iff cost(A,B) \le cost(B,A)

国王游戏、排队打水、最小字典序拼接常用。
比较乘法时注意溢出，用 __int128。

反悔贪心#

先贪心选择，后面发现更优时用堆反悔。

课程安排：按结束时间排序，用堆维护已选课程耗时。
项目选择：可行集合中取收益最大。
本质是维护当前选择集合的最优性。

构造排列#

排列构造常用奇偶分组、循环移位、从两端取数。

避免相邻差为 1：先输出奇数再输出偶数。
字典序最小：从左到右确定每位。
满足 mex 条件：围绕缺失值构造。

博弈构造#

简单博弈先找必败态和转移关系。

win(x)=\exists y \in next(x),\ win(y)=false

Nim 异或和为 0 是必败态。
构造取法时让异或和变为 0。

贪心反例检查#

写完贪心后强制找反例。

局部最优是否可能影响未来选择？
是否存在两个选择当前一样好但未来不同？
能否用交换论证把任意最优解变成贪心解？

高频模板训练卡#

这一组训练卡用于把“05_排序_贪心_构造”转化为赛场识别能力。每张卡都包含题目信号、模板选择、复杂度、反例和实现检查。

卡 1：区间调度#

题目信号：题目要求最少/最多/构造且出现区间调度模型。
优先模板：先尝试区间调度，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为区间调度写一个反例检查和一个正确性证明。

卡 2：区间覆盖#

题目信号：题目要求最少/最多/构造且出现区间覆盖模型。
优先模板：先尝试区间覆盖，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为区间覆盖写一个反例检查和一个正确性证明。

卡 3：反悔贪心#

题目信号：题目要求最少/最多/构造且出现反悔贪心模型。
优先模板：先尝试反悔贪心，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为反悔贪心写一个反例检查和一个正确性证明。

卡 4：Huffman 合并#

题目信号：题目要求最少/最多/构造且出现 Huffman 合并模型。
优先模板：先尝试 Huffman 合并，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为 Huffman 合并写一个反例检查和一个正确性证明。

卡 5：邻项交换排序#

题目信号：题目要求最少/最多/构造且出现邻项交换排序模型。
优先模板：先尝试邻项交换排序，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为邻项交换排序写一个反例检查和一个正确性证明。

卡 6：差值排序#

题目信号：题目要求最少/最多/构造且出现差值排序模型。
优先模板：先尝试差值排序，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为差值排序写一个反例检查和一个正确性证明。

卡 7：最小字典序构造#

题目信号：题目要求最少/最多/构造且出现最小字典序构造模型。
优先模板：先尝试最小字典序构造，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为最小字典序构造写一个反例检查和一个正确性证明。

卡 8：奇偶构造#

题目信号：题目要求最少/最多/构造且出现奇偶构造模型。
优先模板：先尝试奇偶构造，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为奇偶构造写一个反例检查和一个正确性证明。

卡 9：mex 构造#

题目信号：题目要求最少/最多/构造且出现 mex 构造模型。
优先模板：先尝试 mex 构造，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为 mex 构造写一个反例检查和一个正确性证明。

卡 10：括号构造#

题目信号：题目要求最少/最多/构造且出现括号构造模型。
优先模板：先尝试括号构造，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为括号构造写一个反例检查和一个正确性证明。

卡 11：图度数构造#

题目信号：题目要求最少/最多/构造且出现图度数构造模型。
优先模板：先尝试图度数构造，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为图度数构造写一个反例检查和一个正确性证明。

卡 12：排列构造#

题目信号：题目要求最少/最多/构造且出现排列构造模型。
优先模板：先尝试排列构造，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为排列构造写一个反例检查和一个正确性证明。

卡 13：Nim 博弈#

题目信号：题目要求最少/最多/构造且出现 Nim 博弈模型。
优先模板：先尝试 Nim 博弈，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为 Nim 博弈写一个反例检查和一个正确性证明。

卡 14：堆维护可选集#

题目信号：题目要求最少/最多/构造且出现堆维护可选集模型。
优先模板：先尝试堆维护可选集，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为堆维护可选集写一个反例检查和一个正确性证明。

卡 15：排序 + 双指针#

题目信号：题目要求最少/最多/构造且出现排序 + 双指针模型。
优先模板：先尝试排序 + 双指针，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为排序 + 双指针写一个反例检查和一个正确性证明。

卡 16：排序 + 前缀最值#

题目信号：题目要求最少/最多/构造且出现排序 + 前缀最值模型。
优先模板：先尝试排序 + 前缀最值，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为排序 + 前缀最值写一个反例检查和一个正确性证明。

卡 17：贪心 + 证明#

题目信号：题目要求最少/最多/构造且出现贪心 + 证明模型。
优先模板：先尝试贪心 + 证明，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为贪心 + 证明写一个反例检查和一个正确性证明。

卡 18：局部调整#

题目信号：题目要求最少/最多/构造且出现局部调整模型。
优先模板：先尝试局部调整，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为局部调整写一个反例检查和一个正确性证明。

卡 19：极端值优先#

题目信号：题目要求最少/最多/构造且出现极端值优先模型。
优先模板：先尝试极端值优先，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为极端值优先写一个反例检查和一个正确性证明。

卡 20：分组构造#

题目信号：题目要求最少/最多/构造且出现分组构造模型。
优先模板：先尝试分组构造，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为分组构造写一个反例检查和一个正确性证明。

卡 21：按余数构造#

题目信号：题目要求最少/最多/构造且出现按余数构造模型。
优先模板：先尝试按余数构造，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为按余数构造写一个反例检查和一个正确性证明。

卡 22：构造无解判定#

题目信号：题目要求最少/最多/构造且出现构造无解判定模型。
优先模板：先尝试构造无解判定，再写交换论证或不变量。
核心不变量：每一步选择后，剩余问题仍然存在某个最优解。
复杂度目标：排序 O(n log n)，堆贪心 O(n log n)，构造多为 O(n)。
不适用场景：存在未来约束但当前选择没有证明安全时不适用。
实现检查：检查比较器严格弱序、相等情况、无解条件。
边界样例：n=1/2、全相等、极端重复、刚好无解。
训练题型：为构造无解判定写一个反例检查和一个正确性证明。

本章赛前默写任务#

贪心与构造的赛场自检表#

贪心题反例生成建议#

对每一种贪心规则，都尝试构造“当前最优但未来变差”的样例。
对排序贪心，枚举 3 到 6 个元素的所有排列，比较贪心答案和暴力答案。
对区间贪心，重点测试端点相等、完全包含、刚好相接、完全不相交。
对堆反悔贪心，重点测试后出现的大收益元素能否替换前面选择。
对构造题，先暴力枚举小 n 的所有合法答案，从合法答案中观察模式。
如果小 n 无解，大 n 有解，必须把分界条件写进题解。
如果构造依赖奇偶性，必须分别检查奇数 n 和偶数 n。
如果构造依赖模数，必须覆盖所有余数类。
如果答案要求字典序最小，普通“任意构造”往往不够。
构造完成后，写一个 checker 验证输出是否满足题目条件。

05_排序_贪心_构造：详细训练清单#

本清单用于把章节知识拆成可执行的小任务，偏 OI/ACM 赛场使用。

训练点 1：稳定排序#

识别信号：题面出现与“稳定排序”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“稳定排序”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 2：比较器#

识别信号：题面出现与“比较器”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“比较器”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 3：邻项交换#

识别信号：题面出现与“邻项交换”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“邻项交换”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 4：区间调度#

识别信号：题面出现与“区间调度”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“区间调度”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 5：区间覆盖#

识别信号：题面出现与“区间覆盖”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“区间覆盖”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 6：反悔贪心#

识别信号：题面出现与“反悔贪心”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“反悔贪心”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 7：Huffman 合并#

识别信号：题面出现与“Huffman 合并”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“Huffman 合并”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 8：堆维护可选集#

识别信号：题面出现与“堆维护可选集”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“堆维护可选集”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 9：差值排序#

识别信号：题面出现与“差值排序”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“差值排序”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 10：字典序构造#

识别信号：题面出现与“字典序构造”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“字典序构造”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 11：奇偶构造#

识别信号：题面出现与“奇偶构造”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“奇偶构造”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 12：mex 构造#

识别信号：题面出现与“mex 构造”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“mex 构造”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 13：排列构造#

识别信号：题面出现与“排列构造”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“排列构造”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 14：博弈构造#

识别信号：题面出现与“博弈构造”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“博弈构造”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 15：无解判定#

识别信号：题面出现与“无解判定”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“无解判定”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 16：checker 验证#

识别信号：题面出现与“checker 验证”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“checker 验证”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 17：稳定排序#

识别信号：题面出现与“稳定排序”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“稳定排序”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 18：比较器#

识别信号：题面出现与“比较器”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“比较器”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 19：邻项交换#

识别信号：题面出现与“邻项交换”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“邻项交换”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 20：区间调度#

识别信号：题面出现与“区间调度”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“区间调度”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 21：区间覆盖#

识别信号：题面出现与“区间覆盖”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“区间覆盖”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 22：反悔贪心#

识别信号：题面出现与“反悔贪心”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“反悔贪心”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 23：Huffman 合并#

识别信号：题面出现与“Huffman 合并”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“Huffman 合并”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 24：堆维护可选集#

识别信号：题面出现与“堆维护可选集”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“堆维护可选集”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 25：差值排序#

识别信号：题面出现与“差值排序”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“差值排序”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 26：字典序构造#

识别信号：题面出现与“字典序构造”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“字典序构造”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

ぬくぬくうちにゃ💤

第 5 章 排序、贪心与构造#