上一节的贪心按键值排序，一次 sort 就结束。这一节有两个新形状：①贪心的对象是一段区间，排序键从“值”换成“端点”；②贪心要用到“当前最小”，而集合在过程中不断变化，sort 不够了，需要堆。
| 问题 | 排序键 | 每一步怎么决定 | 复杂度 |
|---|---|---|---|
| 区间调度（最多不重叠区间） | 右端点 r 升序 | 当前 l ≥ 上一个 r 就选它 | O(n log n) |
| 区间选点（最少点打中所有区间） | 右端点 r 升序 | 当前 l > 最后一个点，就在 r 处补一个点 | O(n log n) |
| 区间覆盖（最少区间盖满 [1, T]） | 左端点 l 升序 | 在能接上的区间里挑 r 最大的 | O(n log n) |
| 分数背包（可切割） | 性价比 v/m 降序 | 装得下就整堆拿，装不下就切一块 | O(n log n) |
| 合并果子（哈夫曼） | 不排序，每次取最小的两个 | 合并后把新堆放回集合 | O(n log n) |
前四行还是“排一次序、扫一遍”。最后一行不一样：合并出的新堆要重新参与比较，集合是动态的，排一次序就废了。凡是“每步都要取当前最小/最大”的贪心，就用堆。
| 组成 | 含义 / 格式要求 |
|---|---|
priority_queue<T> | 声明一个存放 T 的堆。默认是大根堆：top() 是最大值。 |
q.push(x) | 插入一个元素，O(log n)。堆自己维护顺序，不用再 sort。 |
q.top() | 读堆顶（当前最大/最小元素），O(1)。只读不删。 |
q.pop() | 删除堆顶，O(log n)。它不返回被删的值，想取值必须先 top()。 |
q.size() / q.empty() | 元素个数 / 是否为空。调用 top()、pop() 前必须保证非空。 |
priority_queue<int> q; // 大根堆
for (int x : {3, 1, 4, 1, 5}) q.push(x);
while (!q.empty()) {
cout << q.top() << ' '; // 5 4 3 1 1
q.pop(); // 想取值就先 top() 再 pop()
}cout << q.pop() 直接编译错误：pop() 的返回类型是 void。
堆里元素的类型必须可比较：int、pair 可以，struct 必须重载 operator<。
| 组成 | 含义 / 格式要求 |
|---|---|
三个模板参数 | ①元素类型 int ②底层容器 vector<int> ③比较器 greater<int>。三个都要写，少一个就编译报错。 |
greater<int> | 来自 <functional>（bits 里已包含）。它表示“大的排在后面”，于是小的浮到堆顶。 |
为什么不能只写两个 | 第二个参数位置固定是容器，把比较器塞进去会报一大串模板错误，错误信息往往指向 <bits/stl_queue.h>。 |
等价写法 | 把 -x 存进大根堆再取负；只适合 long long（int 的 -x 会溢出）。 |
priority_queue<int, vector<int>, greater<int>> q; // 小根堆
for (int x : {3, 1, 4, 1, 5}) q.push(x);
while (!q.empty()) { cout << q.top() << ' '; q.pop(); } // 1 1 3 4 5口诀：默认大根堆，加 greater 变小根堆。自定义优先级时别硬塞 greater，用 operator< 更清楚。
| 组成 | 含义 / 格式要求 |
|---|---|
为什么写在结构体里 | priority_queue 用 operator< 比较元素。写在结构体里，堆就能直接拿来用。 |
const Node &o | 按引用传，避免拷贝；必须 const，因为堆内部用常量引用比较。 |
末尾的 const | 表示比较不修改自身。漏写会编译失败，报错位置在模板深处，很难读。 |
return w > o.w | operator< 返回 true 表示 this 的优先级更低（排在 o 后面）。写 w > o.w，于是 w 小的反而在堆顶。 |
与 sort 的 cmp 方向相反 | cmp 回答“a 是否在前”，operator< 回答“this 是否在后”。同一个不等式，两处要反过来写，这是本节最高频的错误。 |
struct Task {
int w;
// 想让 w 小的在堆顶 -> 写 w > o.w（与 sort 的 cmp 反着写）
bool operator<(const Task &o) const { return w > o.w; }
};
priority_queue<Task> q;
q.push({3}); q.push({1}); q.push({4});
cout << q.top().w; // 1口诀：cmp 写“谁在前”，operator< 写“谁在后”。堆顶永远是“比较意义下最大”的元素。
有 n 场比赛，第 i 场从 a_i 时刻开始、b_i 时刻结束。同一时刻只能参加一场，但一场可以在结束的同一时刻立刻开始另一场。求最多能参加多少场。
输入格式：第一行一个整数 n；接下来 n 行，每行两个整数 a_i、b_i。
输出格式：一行一个整数，表示最多参加的场数。
数据范围：1 ≤ n ≤ 10⁶，0 ≤ a_i < b_i ≤ 10⁶。
候选 ①：按开始时间 a_i 升序。反例：三场 [0,100]、[1,2]、[3,4]。先选 [0,100]，剩下两场都被它盖住，只能 1 场；最优是 [1,2] 和 [3,4]，2 场。错因：开始早不代表占得少。
候选 ②：按区间长度 b_i − a_i 升序。反例：[0,6]、[6,10]、[0,10]。最短的 [6,10] 先选，另两场都接不上，只能 1 场；最优是 [0,6] + [6,10] 共 2 场。错因：短区间可能卡在中间，把两边都切断。
候选 ③：按结束时间 b_i 升序。这个对。设排序后第一个区间是 I₁ = [l₁, r₁]，r₁ 是所有右端点里最小的。任取一个最优解，它的第一场是 J = [l_J, r_J]，必有 r_J ≥ r₁。把 J 换成 I₁：最优解的第二场 K 满足 l_K ≥ r_J ≥ r₁，所以 I₁ 与 K 不冲突，场数不变。于是存在一个最优解，第一场就是 I₁——贪心的第一步是安全的。删掉与 I₁ 冲突的区间，剩下问题同构，归纳即可。
落点是一句话：越早结束，剩下的时间越多，所以它不吃未来的资源——命中上一节的“交换不变差”。
sort(a + 1, a + n + 1, cmp); // cmp：右端点升序
int ans = 0, last = 0;
for (int i = 1; i <= n; ++i)
if (a[i].l >= last) { ++ans; last = a[i].r; } // 接得上就选，选了才更新n 到 10⁶，数组必须开全局（放静态区），并且关掉 cin 同步。
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n;
struct Seg { int l, r; } a[N];
// 唯一的贪心决策：按右端点升序
bool cmp(const Seg &x, const Seg &y) {
if (x.r != y.r) return x.r < y.r; // 主键：越早结束越优先
return x.l < y.l; // 次键：保证严格弱序
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i].l >> a[i].r;
sort(a + 1, a + n + 1, cmp); // O(n log n)，n = 10^6 也能过
int ans = 0, last = 0; // last = 上一场的结束时刻；时刻都 >= 0，初值 0 安全
for (int i = 1; i <= n; ++i) {
if (a[i].l >= last) { // 接得上（等号不能少：t 结束、t 开始是允许的）
++ans;
last = a[i].r; // 只有真的选了才更新，这是贪心的"落子"
}
}
cout << ans << '\n';
return 0;
}| 代码片段 | 含义与理由 |
|---|---|
struct Seg { int l, r; } a[N]; | 把一场比赛存成区间。n 到 10⁶，数组开全局：局部数组放在栈上会直接爆栈（RE）。 |
if (x.r != y.r) return x.r < y.r; | 整个算法只有这一行在做决策。换成 x.l < y.l，得到的就是候选 ① 的错误算法。 |
int ans = 0, last = 0; | last 是“已选区间中最晚的结束时刻”，初值 0 因为题目保证时刻非负，等价于“第一场随时能开始”。 |
if (a[i].l >= last) | 能接上就选。等号是关键：t 时刻结束的那场与 t 时刻开始的下一场不冲突。 |
last = a[i].r; | 选了才更新。更新的是 r 而不是 max(last, r)：按 r 升序后 a[i].r 一定 ≥ last。 |
cout << ans; | 答案是场数，不是总时长、不是总覆盖长度。别把 ++ans 写成 ans += a[i].r - a[i].l。 |
经典模型：给定 n 个闭区间，选最少的点，使每个区间至少包含一个点。排序键一模一样——右端点升序。
维护最后一个放下的点 last（初值 −∞）。按 r 升序扫描，若 last 没落在当前区间 [l, r] 里就必须再放一个点；放哪里？放右端点 r，它最靠右，能顺带覆盖更多后面的区间。判断条件可以简化成一行 l > last：按 r 升序保证 last ≤ r，所以只要 l ≤ last，就必有 last ∈ [l, r]。
// 接在"按右端点排序"之后，替代上一题的判断
int cnt = 0;
long long last = -1; // 还没有放点；坐标 >= 0，-1 相当于 -inf
for (int i = 1; i <= n; ++i) {
if (a[i].l > last) { // 上一个点没打中这个区间
++cnt;
last = a[i].r; // 在右端点补一个点，覆盖尽量多的后续区间
}
}
// cnt 就是最少点数两题并排看：调度题问“能不能接上”（l ≥ 上一场的 r），选点题问“有没有被点到”（l > 最后一个点）。“越靠右越不吃未来资源”这一句同时支撑两个算法。
n 堆物品（重量 m_i、价值 v_i）和容量 T，每堆可以只取一部分，价值按比例算，求最大价值。这是“能切割”的背包，贪心成立；0/1 背包不能切，贪心不成立（上一节的反例库）。
排序键：性价比 v_i / m_i 降序。容量可看成 T 个 1 单位的格子，每个格子都该填“每单位最贵”的东西，所以贵的先拿满。能整堆拿就整堆拿，装不下就把剩余容量按比例切一块然后结束。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n;
long long cap; // 剩余容量
struct Item { long long m, v; } a[N];
// 性价比 v/m 降序：交叉相乘代替除法，避开浮点误差
bool cmpRatio(const Item &x, const Item &y) {
return x.v * y.m > y.v * x.m; // v, m <= 10^6 时乘积 <= 10^12，long long 安全
}
int main() {
cin >> n >> cap;
for (int i = 1; i <= n; ++i) cin >> a[i].m >> a[i].v;
sort(a + 1, a + n + 1, cmpRatio);
double ans = 0;
for (int i = 1; i <= n && cap > 0; ++i) {
if (a[i].m <= cap) { // 整堆装得下，全拿
cap -= a[i].m;
ans += a[i].v;
} else { // 只剩部分空间，按比例切一块
ans += 1.0 * a[i].v * cap / a[i].m;
cap = 0;
}
}
cout << fixed << setprecision(2) << ans << '\n';
return 0;
}不要写 x.v / x.m > y.v / y.m：double 比较有误差，可能把相等判成不等，而且 m = 0 时会除零。
有 n 堆果子，第 i 堆有 a_i 个。每次可以把两堆合并成一堆，消耗的体力等于两堆果子数之和。经过 n − 1 次合并后只剩一堆，求消耗的体力总和的最小值。
输入格式：第一行一个整数 n；第二行 n 个整数 a_1 … a_n。
输出格式：一行一个整数，即最小体力消耗。
数据范围：1 ≤ n ≤ 10⁴，1 ≤ a_i ≤ 2×10⁴，答案保证小于 2³¹。
先看清代价的结构：一堆果子被合并 d 次，它的数量就被算进总代价 d 次。所以重的应该少被合并（离根浅），轻的应该多被合并（离根深）。把每次合并画成一棵二叉树，总代价 = Σ a_i × 深度_i。
交换论证：最优树里最轻的两堆一定在最深层且互为兄弟。若最轻的叶子不在最深层，把它与最深的叶子交换，小权值下移、大权值上移，WPL 只会变小，与最优性矛盾。所以先合并最轻的两堆不损失最优性，剩下问题同构，归纳即可。
实现上有个关键点：合并出的新堆必须重新参与比较。排一次序就固定的做法是错的（1、2、9 合并出 3 之后，3 比 9 小，下一轮该先碰它）。集合动态变化，所以用堆：每次 top 两次、pop 两次、push 一次，n − 1 轮，总 O(n log n)。这是本课程第一次出现“贪心 + 数据结构”。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// 三个模板参数：元素类型、底层容器、比较器。greater 表示小的优先 -> 小根堆
priority_queue<int, vector<int>, greater<int>> q;
for (int i = 0; i < n; ++i) {
int w;
cin >> w;
q.push(w);
}
long long cost = 0; // 本题保证答案 < 2^31，但用 long long 不亏
while (q.size() > 1) { // 合并 n-1 次，剩 1 堆时结束
int x = q.top(); q.pop(); // 当前最轻的两堆
int y = q.top(); q.pop();
cost += x + y; // 这次合并消耗的体力
q.push(x + y); // 新堆放回集合，参与后面的合并
}
cout << cost << '\n';
return 0;
}| 代码片段 | 含义与理由 |
|---|---|
priority_queue<int, vector<int>, greater<int>> q; | 小根堆：top() 始终是最轻的一堆。用默认大根堆会先合并最大的两堆，答案偏大。 |
while (q.size() > 1) | 合并 n − 1 次，剩 1 堆时停。写成 while (!q.empty()) 会在最后一轮第二次 pop 时取空堆。 |
int x = q.top(); q.pop(); int y = q.top(); q.pop(); | 连续取两个最小值。必须先 top 再 pop，两句不能合并（pop 没有返回值）。 |
cost += x + y; | 这次合并的体力消耗就是两堆之和，也是这棵子树的根权值。 |
q.push(x + y); | 新堆必须放回去。漏了这一行，下一轮会比较到已经不存在的旧值，答案偏离。 |
在空堆上 q.top() 或 q.pop()：未定义行为，通常 RE（段错误）。合并果子的循环条件必须是 q.size() > 1。
合并果子错用大根堆（漏写 greater）：每轮合并最大的两堆，样例 3 / 1 2 9 会输出 23 而不是 15 → WA。这种错最容易藏在“样例过了”的错觉后面，一定要用这组数据验证。
operator< 写成 return w < o.w; 以为是小根堆：堆顶其实是最大值 → WA，而且结构体题通常没有小样例能暴露它。
cmp 或 operator< 里用 <=、>=：破坏严格弱序，std::sort 可能越界写内存 → RE；开 -fsanitize 会报 invalid comparator。
区间调度按左端点或区间长度排序，用 [0,100]、[1,2]、[3,4] 或 [0,6]、[6,10]、[0,10] 一测就 WA；n = 10⁶ 时不关 cin 同步会 TLE，把 10⁶ 的数组开在 main 里会 RE（爆栈）。
关掉页面，把 P1803 的代码从零敲一遍并提交，确认样例输出 2。
改一改①：把 a[i].l >= last 的等号去掉，用数据 2 / 1 2 / 2 3 试。正确答案是 2（第一场 2 时刻结束，第二场 2 时刻开始，可以接着打），改完变成 1。
改一改②：合并果子把 greater<int> 删掉变成大根堆，跑 3 / 1 2 9，看答案从 15 变成 23。亲手体会一次“堆的方向决定贪心方向”。
把每次合并画成一个新结点，两个孩子是参与合并的两堆。n 堆最终合并成一棵树：叶子是原始堆，内部结点是合并出来的新堆，共 n − 1 个内部结点。某堆果子被合并 d 次，它的数量就在 d 个内部结点的权值里各出现一次，所以
总代价 = Σ（内部结点权值）= Σ a_i × d_i，d_i 是叶子的深度。这个量叫 带权路径长度 WPL，也就是哈夫曼编码里的平均码长项。例：a = 1, 2, 3, 4，合并 1+2 = 3、再合并 3+3 = 6、最后 6+4 = 10，总代价 19；检验深度：1、2 深度 3，3 深度 2，4 深度 1，1×3 + 2×3 + 3×2 + 4×1 = 19。
为什么“取最小的两堆”最优？最轻的两堆在最优树里一定是最深的一对兄弟；否则把它们与最深的叶子交换，小权值下移、大权值上移，WPL 严格变小，与最优性矛盾。
规模：n 堆合并 n − 1 次，每次堆操作 O(log n)，总 O(n log n)。树深最坏可到 n − 1，代价不能按 log n 估。P6033（n 到 10⁷）必须用 long long 并换 O(n) 做法。
有 N 个受损建筑，只有一个修理工。修第 i 个建筑需要 T1_i 秒，如果它在 T2_i 秒之内还没有修完就会报废。修理工一次只能修一个，求最多能抢修多少个建筑。
输入格式：第一行一个整数 N；接下来 N 行，每行两个整数 T1_i、T2_i。
输出格式：一行一个整数 S，表示最多能抢修的建筑数。
数据范围：1 ≤ N < 150000，1 ≤ T1_i < T2_i < 2³¹。
报废时间早的建筑必须优先处理，否则一定来不及。先按 T2 升序排序，再想“排好序之后怎么决定修不修”。
如果某一刻发现总时间已经超过当前建筑的报废时间，说明前面选多了——该从已选的里面去掉一个，去掉哪个最划算？
去掉“最费时”的那个能让总时间降得最多，而建筑个数不变。用一个大根堆维护已选建筑的修复时间。
排序。按报废时间 T2 升序。若存在一种方案能修 k 个，把它们按 T2 升序排列也不会违反任何报废时间。
依次处理每个建筑，维护：已选集合 S、总修复时间 sum、一个存 S 中所有 T1 的大根堆。
若 sum + T1_i ≤ T2_i：直接加入 S。它在 S 里最后修，前面已选建筑的完成时间不变，所以只要它自己赶得上，整个 S 仍然合法。
若 sum + T1_i > T2_i：加不进第 |S| + 1 个，最多只能保持 |S| 个。此时如果堆顶（S 里最费时的）> T1_i，就用当前建筑替换它：个数不变、sum 变小；而且当前建筑 T2 最大、排在最后，替换后每个前缀的完成时间都不会变大，合法性保住。若堆顶 ≤ T1_i，替换只会让 sum 更大，什么也不做。
最后答案就是堆的大小。复杂度 O(N log N)，N = 1.5×10⁵ 轻松过。
#include <bits/stdc++.h>
using namespace std;
const int N = 150005;
int n;
struct Build { int t1, t2; } a[N];
// 按报废时间升序：越早报废越先考虑
bool cmp(const Build &x, const Build &y) {
if (x.t2 != y.t2) return x.t2 < y.t2;
return x.t1 < y.t1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i].t1 >> a[i].t2;
sort(a + 1, a + n + 1, cmp);
priority_queue<int> q; // 大根堆：已选建筑的修复时间，堆顶最费时
long long sum = 0; // 已选建筑的总耗时，最大约 1.5e5 * 2^31，必须 long long
for (int i = 1; i <= n; ++i) {
if (sum + a[i].t1 <= a[i].t2) {
sum += a[i].t1; // 赶得上，直接修
q.push(a[i].t1);
} else if (!q.empty() && q.top() > a[i].t1) {
// 赶不上：用当前建筑换掉已选里最费时的那个，数量不变、总时间变小
sum -= (long long)q.top() - a[i].t1;
q.pop();
q.push(a[i].t1);
}
// 否则当前建筑直接放弃：换了只会更慢
}
cout << q.size() << '\n'; // 堆里剩几个就是最多能修几个
return 0;
}| 片段 | 作用 |
|---|---|
sort(a + 1, a + n + 1, cmp); | 按报废时间排序。这一步定下了“修的顺序就是处理顺序”，后面所有判断都基于这个顺序。 |
priority_queue<int> q; | 这里要的是大根堆：每次想知道“已选里最费时的是谁”，所以用默认的 priority_queue，不要加 greater。 |
if (sum + a[i].t1 <= a[i].t2) | 当前建筑排在这一批的最后修，只要它的完成时刻不超过自己的报废时间，前面已选的完成时刻都没变，整批仍合法。 |
sum -= (long long)q.top() - a[i].t1; | 先减后加写成一句。括号里显式转 long long，避免 int 减法在极端数据下出问题。 |
cout << q.size(); | 答案不是 sum、不是 cnt，而是集合大小。q.size() 的类型是 size_t，直接输出没问题。 |