贪心与堆

“每次都挑眼前最好的”，听起来无比轻松，但这也是信奥考场上爆零最频繁的重灾区。

最便宜的往往隐藏着巨额隐性代价，耗时最短的可能会横切阻断更优的连击，数值最大的也未必值得你第一时间锁定。贪心算法的软肋从来不是“目光短浅”，而在于你能不能在考场上说服自己：这一步迈出去，不仅眼前赚了，而且通往全局最优的那扇大门依然死死敞开着？

本讲我们彻底抛弃模棱两可的“玄学直觉”，聚焦两类在竞赛中能从数学与物理层面完全证死的经典贪心模型：不相交区间的最优调度与哈夫曼式堆合并。并在文末打通思维链路，推演至更高阶的“反悔贪心”，建立一套真正坚固的贪心推导框架。

一、贪心的痛点：直觉为什么总在悄悄翻车？

我们先来看一个最现实的场景：

教室活动安排问题：有一间多媒体教室，同一时刻只能承接一场活动。现在手头有 $n$ 个活动申请，每个活动占用时间区间为 $[l, r)$（左闭右开，即前一场活动在 $r$ 结束，后一场活动在 $r$ 开启是可以无缝衔接的）。目标是：安排尽可能多的活动场次。

面对这个问题，绝大部分初学者的脑海里会瞬间跳出两种看似极其科学的“贪心策略”：

1. 策略 A（先来后到）：谁开始得早，我就先给谁排。
2. 策略 B（勤俭节约）：哪场活动持续时间最短，占教室时间最少，我就先选谁。

别急着敲键盘写代码，我们拿两组极小的数据直接让这两种直觉当场翻车。

1. 翻车现场 1：最早开始，可能一脚踩死一整片

考虑以下 4 个活动区间：

• 活动 1：$[0, 10)$
• 活动 2：$[1, 2)$
• 活动 3：$[2, 3)$
• 活动 4：$[3, 4)$

如果按照“最早开始”的策略 A，你会一眼相中 $[0, 10)$。然而这一场活动就霸占了整间教室，最终你只能安排 1 场。 但只要你稍微抬头往后看，活动 2、3、4 完全可以背靠背无缝接力，轻松塞下 3 场。

直觉盲区：开门最早，绝不代表它能最早把场地腾出来交还给下一批人。

2. 翻车现场 2：时长最短，可能横插一杠双向断路

再看以下 3 个活动：

• 活动 1：$[0, 3)$（时长 3）
• 活动 2：$[3, 6)$（时长 3）
• 活动 3：$[2, 4)$（时长 2）

如果按照“时长最短”的策略 B，活动 3 只有 2 个小时，看起来性价比最高。但只要你选了它，它就会硬生生地跨在中间，把 $[0, 3)$ 的尾巴和 $[3, 6)$ 的头全部撞得粉碎，最终你只能安排 1 场。 反之，如果我们完全无视这个最短的“诱惑”，选活动 1 和活动 2，可以稳稳拿下 2 场。

直觉盲区：短区间虽然自私地省下了自身的时间，但它横亘的位置极具破坏性。我们真正需要为未来储备的资源，是更早获得空闲的起跑线，而不是单纯这场活动自己开了多久。

二、破局法则：按结束时间贪心的微扰与交换论证

既然“开始早”和“自身短”都靠不住，破局的唯一物理逻辑呼之欲出：

核心法则：将所有活动按照结束时间（右端点 $r$）从小到大排序；每次只要当前活动的开始时间不早于上一场已选活动的结束时间，就立刻收入囊中。

1. 为什么“结束最早”一定稳赚不赔？（交换论证）

在考场上，我们要敢于用微扰/交换论证法（Exchange Argument）来证明贪心决策的绝对正确性：

假设全集活动中，结束时间最早的活动叫做 $A$。 此时，假定天底下存在一个我们暂且未知的神级最优解，它挑选出的活动序列是：

现在我们要问：如果 $B$ 本身不是 $A$，我们强行把 $B$ 踢出去，换成 $A$，这个方案会变差吗？

• 根据我们的排序定义，$A$ 是所有候选活动中结束得最早的，因此必有：
  $$r_A \le r_B$$
• 原方案 $S$ 中排在 $B$ 后面的活动（例如 $C$），由于原本就能兼容 $B$，必然满足 $l_C \ge r_B$。
• 既然 $l_C \ge r_B$，再结合 $r_B \ge r_A$，立即推导出：
  $$l_C \ge r_A$$

这意味着：把开局的第一场活动强行偷换成 $A$ 之后，$A$ 不仅能被放进去，而且它给后续所有活动腾出的空闲时间只会更早、更充裕，绝对不会挤占 $C$ 以及后续任何一场活动的时间！

替换之后，新方案包含的活动总场数完全没有减少。这就铁证如山地说明： 在所有的最优解中，一定至少存在一个最优解，它的第一步就是选择 $A$。

既然选 $A$ 绝不吃亏，我们就放心大胆地锁定 $A$；随后教室在 $r_A$ 时刻空出，剩下的问题变成了在 $[r_A, +\infty)$ 范围内面对完全相同结构的子问题，一路贪心推导即可。

2. 模拟手推：指针是怎样向前推进的？

给定 5 个活动区间：$[1, 4), [3, 5), [0, 6), [5, 7), [7, 8)$。

1. 第一步（排序）：按结束时间 $r$ 升序排列：
   • 活动①：$[1, 4)$
   • 活动②：$[3, 5)$
   • 活动③：$[0, 6)$
   • 活动④：$[5, 7)$
   • 活动⑤：$[7, 8)$
2. 第二步（扫描决策）：
   • 考察① $[1, 4)$：第一场必然选它。记录当前教室占用截止位 last = 4，已选 $1$ 场。
   • 考察② $[3, 5)$：它的开始时间 $3 < \text{last}(4)$，撞车冲突，果断抛弃！（极其关键：跳过它时，绝不能更新 last！last 记录的是方案真实占用的终点，而不是你路过的风景）。
   • 考察③ $[0, 6)$：开始时间 $0 < 4$，冲突，跳过。
   • 考察④ $[5, 7)$：开始时间 $5 \ge 4$，完美衔接！收入方案，更新 last = 7，已选 $2$ 场。
   • 考察⑤ $[7, 8)$：开始时间 $7 \ge 7$，刚好无缝压哨！选它，更新 last = 8，已选 $3$ 场。
3. 最终最多能安排 3 场。

三、实战标程一：最多安排活动数

1. 输入输出协议与数据范围

• 输入格式：第一行一个整数 $n$，表示活动总数。接下来 $n$ 行，每行两个整数 $l, r$，代表一个活动的开始与结束时间。
• 输出格式：一个整数，表示最多能同时兼容的活动总数。
• 数据范围：$0 \le n \le 2\times 10^5$，$-10^9 \le l < r \le 10^9$。

💡 考场避坑细节： 本题的活动时间坐标允许为负数（例如 $[-5, -3)$ 完全合法）。千万不要习惯性地把 last 随手初始化为 0，否则任何在时间小于 0 的活动都会被你误判为“冲突”而全部漏掉！代码中设置一个布尔变量 chosen 代表是否完成了首场选择，比硬写一个负无穷更安全、更规范。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;

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;
}

void solve(){
	int n;
	if(!(cin>>n)) return;
	for(int i=1;i<=n;i++){
		cin>>a[i].l>>a[i].r;
	}
	
	// 1. 按照结束时间升序排序
	sort(a+1,a+1+n,cmp);
	
	int ans=0;
	int last=0;
	bool chosen=false; // 标记是否已经敲定了第一场
	
	// 2. 单向线性扫描
	for(int i=1;i<=n;i++){
		if(!chosen || a[i].l>=last){
			ans++;
			last=a[i].r; // 推进已选占用的最右边界
			chosen=true;
		}
	}
	
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

• 时间复杂度：排序耗时 $O(n \log n)$，后续线性扫描 $O(n)$，总时间复杂度为 $O(n \log n)$，可以稳稳跑过 $2 \times 10^5$。
• 空间复杂度：存储数组占用 $O(n)$。

2. 思维警惕：如果每场活动收益不同，还能按右端点贪心吗？

绝对不能！ 假设活动 A 为 $[0, 2)$ 收益 1 元；活动 B 为 $[2, 4)$ 收益 1 元；活动 C 为 $[0, 4)$ 收益 100 元。 如果你依旧按照结束时间贪心，你一定会选 A 和 B，得到区区 2 元；而放弃全场最优的 C（100 元）。 这是因为交换论证在此处彻底失效了：虽然 A 腾出空间更早，但替换 C 带来的收益亏损（$-99$）无法被未来弥补。带权区间选择问题必须使用离散化 + 动态规划 + 二分查找（$dp[i] = \max(dp[i-1], dp[prev] + w_i)$）来解决。切记：算法由数学本质决定，千万别看题面带了左右端点就乱套模板！

四、最小合并费用：为什么小的要先碰面？

我们切换到另一个经典的物理世界：

果子合并/材料合成问题：地面上有 $n$ 堆材料，每堆重量已知。每次你可以任意挑选其中的两堆合成一个新堆，合成所消耗的体力（费用）恰好等于这两堆材料的重量之和；合成后的新堆重量也等于这个和，并放回地面。如此重复操作，直到地面上只剩下唯一的一大堆。求将所有材料合成一堆所需的最小总费用。

拿重量为 $[1, 2, 3, 4]$ 的四堆材料来手推两种截然不同的策略：

• 策略一：大的先合并
  • 第一步：挑最大的 4 和 3 合并，产生新堆 7，支付费用 7；剩余 $[1, 2, 7]$。
  • 第二步：挑 7 和 2 合并，产生新堆 9，支付费用 9；剩余 $[1, 9]$。
  • 第三步：挑 9 和 1 合并，产生最终堆 10，支付费用 10。
  • 总费用：$7 + 9 + 10 = \mathbf{26}$。
• 策略二：小的先合并
  • 第一步：挑最小的 1 和 2 合并，产生新堆 3，支付费用 3；剩余 $[3, 3, 4]$。
  • 第二步：挑最小的 3 和 3 合并，产生新堆 6，支付费用 6；剩余 $[4, 6]$。
  • 第三步：合并 4 和 6，产生最终堆 10，支付费用 10。
  • 总费用：$3 + 6 + 10 = \mathbf{19}$。

1. 物理本质透视：合并是一棵倒挂的二叉树

最终两套方案合成的终极总重量都是 10，为什么策略二能凭空省出 7 点费用？

我们把每一次合并过程画成一个二叉树结构：

• 最初的每一堆材料，就是这棵二叉树上的叶子节点；
• 每一次合并操作，就是在为它们建立一个父节点；
• 父节点所代表的重量，会被继续向上送去参与更高层的合并。

这就导出了一个至关重要的物理结论： 每一个初始叶子节点 $w_i$，在整个合并历史中被累计收税的次数，恰好等于它在树中所处的深度 $d_i$（约定根节点深度为 0）！

因此，合并这 $n$ 堆材料的最终总费用，可以用极其优美的贡献法写为：

在策略二的最优合并树中：

• 节点 1 经历了 3 次合并（深度为 3），贡献为 $1 \times 3 = 3$；
• 节点 2 经历了 3 次合并（深度为 3），贡献为 $2 \times 3 = 6$；
• 节点 3 经历了 2 次合并（深度为 2），贡献为 $3 \times 2 = 6$；
• 节点 4 仅经历了 1 次合并（深度为 1），贡献为 $4 \times 1 = 4$；
• 累加总和：$3 + 6 + 6 + 4 = \mathbf{19}$。

2. 深度交换论证：为什么每次必须挑最小的两堆？

看懂了“费用 = 深度 $\times$ 重量”，答案就彻底明朗了： 我们必须让重量最大的叶子尽可能停留在浅层（少乘几次），重量最小的叶子沉到最深层（多乘几次）。

我们用严格的数学交换来论证： 在一棵任意给定的合法合并树中，必然存在深度最深的一对兄弟叶子节点（因为如果最深层不是成对的兄弟叶子，树的结构就无法闭合）。 设当前最深层的深度为 $d_{\max}$，上面的两个叶子为 $A$ 和 $B$。 若当前全集中权重最小的两个元素 $x$ 和 $y$ 不在这对最深兄弟上，而是分别处于深度为 $d_1, d_2$ 的位置（必有 $d_1 \le d_{\max}$ 且 $d_2 \le d_{\max}$）。

设原本位于最深层的某个较大元素为 $z$（$x \le z$）。若我们将 $x$ 与 $z$ 交换位置： 交换前对总费用的贡献：$x \cdot d_1 + z \cdot d_{\max}$ 交换后对总费用的贡献：$x \cdot d_{\max} + z \cdot d_1$ 费用的变化差值（新 - 旧）为：

这一步交换绝对不会让总费用变多！ 同理，再将次小元素 $y$ 交换到其兄弟位置，总费用同样单调不增。 由此得证：一定存在一个最优方案，最深层的那一次合并，正是全局最小的两个元素 $x$ 和 $y$。

既然它们俩注定最先合并，我们就可以将它们合成为一个重量为 $x+y$ 的超级单质，原问题完美缩减为规模为 $n-1$ 的同构子问题。

五、为什么必须请出“堆”？

有些同学会问：“既然每次要挑最小的两个，我开局直接对原数组从小到大 sort 一次，然后从左到右两两合并，不就结了吗？”

大错特错！ 看这个数据：$[1, 2, 100, 100]$。

1. 第一轮你合成了 1 和 2，产生新元素 3。此时地上的元素变成了 $[3, 100, 100]$。
2. 下一轮最小的两个元素是谁？是 3 和 100，而不是你原数组中排在后面的那两个 100！

每完成一次合并，就会动态诞生一个新的权值。这个新权值必须立刻放回池子中，和所有老权值一同重新竞争“谁最小”。 如果每轮都重新暴力排序，时间复杂度将飙升至 $O(n^2 \log n)$，必定 TLE 爆零。

我们需要一个能够在 $O(\log n)$ 内动态弹入新元素、并随时在 $O(1)$ 查出当前最小值的数据结构——这就是小根堆（Min-Heap）。

在 C++ STL 中，优先队列默认是大根堆（降序）。写成小根堆必须挂上后两个参数： priority_queue<int, vector<int>, greater<int>> q;

六、实战标程二：最小合并费用

1. 输入输出协议与数据范围

• 输入格式：第一行一个整数 $n$。第二行 $n$ 个用空格隔开的非负整数，表示各堆初始重量。
• 输出格式：一个整数，表示完成合并所需的最小总费用。
• 数据范围：$1 \le n \le 10^5$，$0 \le w_i \le 10^6$。

💡 考场避坑细节：

1. 单堆特判：当 $n = 1$ 时，本身就已经是一堆了，根本不需要发生任何合并！此时答案为 0，千万不能把唯一的那个元素重量输出去。
2. 零权处理：数据范围允许重量为 0。0 是合法的物理堆，绝不能在读入时用 if(x > 0) 把它过滤掉。
3. 防溢出：即使单个重量 $10^6$，但在 $n = 10^5$ 规模下，合并总费用会迅速突破 $2^{31}-1$，必须全程开启 long long。

#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
	int n;
	if(!(cin>>n)) return;
	
	// 定义小根堆：随时抓取当前池子里的最小值
	priority_queue<int,vector<int>,greater<int>> q;
	for(int i=1;i<=n;i++){
		int w;
		cin>>w;
		q.push(w);
	}
	
	int ans=0;
	// 每次从堆中提取两个最小的元素合并，直到只剩一堆
	while(q.size()>1){
		int x=q.top(); q.pop();
		int y=q.top(); q.pop();
		
		int sum=x+y;
		ans+=sum;      // 累计本次合并支付的体力/费用
		q.push(sum);   // 将合成的新堆重新扔进池中重新参与排序
	}
	
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

• 时间复杂度：一共进行 $n-1$ 次合并，每次合并包含 2 次 pop 和 1 次 push，单次耗时 $O(\log n)$。总时间复杂度为 $O(n \log n)$。
• 空间复杂度：堆中最多同时容纳 $n$ 个节点，空间复杂度为 $O(n)$。

2. 拓展思考：如果题目规定“只能合并相邻两堆”呢？

如果题面加上了限制条件——“只能挑选相邻的两堆进行合并”，这道题的贪心体系瞬间全盘崩溃！ 因为最小的两堆可能相隔千里，它们根本无法直接碰面；交换叶子节点的自由度被相邻约束彻底锁死。此时问题转化为经典的石子合并（区间 DP）模型，必须使用 $dp[i][j] = \min(dp[i][k] + dp[k+1][j]) + sum(i, j)$ 在 $O(n^3)$ 或四边形不等式优化到 $O(n^2)$ 下求解。

七、区间贪心的另外两副面孔：区间覆盖与最少分组

在前面的【教室活动安排问题】中，我们解决的是“选出尽可能多互不冲突的活动”。这属于不相交区间调度。但走进考场，区间类贪心常会换上另外两副面孔，如果我们死记“右端点排序”，就会直接撞上南墙。

1. 区间覆盖问题：用最少区间织密目标线段

问题模型：给定目标闭区间 $[S, T]$ 以及 $n$ 个可选闭区间 $[l_i, r_i]$。请选出数量最少的区间，使得它们的并集能够完全覆盖目标区间 $[S, T]$。如果无论怎么选都无法完全覆盖，输出 $-1$。

为什么不能再按右端点排序？

很多同学顺手又敲了 cmp 比较右端点，结果发现无论怎么贪心都是错的： 如果你挑了一个结束时间很早的区间，由于你根本没有控制它的左端点，这个区间很可能孤悬在半空中，既接不上起点 $S$，也接不上前一个区间的屁股，中间硬生生撕开一道覆盖空白。

面对覆盖任务，我们最先要守住的底线是：绝不能断层。

贪心法则与关键推导

1. 排序基准：将所有候选区间按照左端点 $l$ 从小到大升序排序。
2. 状态与物理意义：维护一个变量 cur，表示当前已经被连续覆盖到的最右边界。初始时必须覆盖起点，所以 cur = S。
3. 决策逻辑： 在所有能够与当前覆盖区无缝接轨（即满足 $l_i \le cur$）的候选区间中，挑出那个右端点 $r_i$ 能够向右延伸得最远的区间！
   • 为什么这样最优？既然它们都能接上 cur 不漏空，那么右端点伸得越长，就给未来留出了越开阔的起跑线，后续需要补充的区间数量就绝不可能变多。
4. 推进与无解判定：
   • 先比较 $r_{\max}$ 与当前的 cur：若 $r_{\max} \le cur$，说明没有任何新区间能继续向右拓宽半步，中途彻底断层，直接判定无解返回 $-1$；
   • 否则再将 cur 推进到 $r_{\max}$，已选计数 $+1$；
   • 一旦 $cur \ge T$，说明目标区间已被完全锁死，贪心立即胜利收工。

模拟手推：一步步向右推进

目标线段 $[1, 10]$。给出 5 个候选区间：$[1, 3], [2, 6], [5, 8], [7, 11], [8, 12]$。 初始 cur = 1，已选 $0$ 个。

• 第一轮：左端点 $\le 1$ 的只有 $[1, 3]$。最大延伸右端点为 $3$。选中它，cur 推进到 $3$，已选 $1$ 个。
• 第二轮：左端点 $\le 3$ 的候选有 $[2, 6]$（因为 $2 \le 3$）。最大延伸右端点为 $6$。选中它，cur 推进到 $6$，已选 $2$ 个。
• 第三轮：左端点 $\le 6$ 的候选有 $[5, 8]$（$5 \le 6$）。最大延伸右端点为 $8$。选中它，cur 推进到 $8$，已选 $3$ 个。
• 第四轮：左端点 $\le 8$ 的候选有 $[7, 11]$ 和 $[8, 12]$。其中 $[8, 12]$ 延伸最远达 $12$。选中它，cur 推进到 $12 \ge 10$，已选 $4$ 个。
• 达到目标终点，答案为 4。

实战标程：最少区间覆盖

输入输出协议与数据范围

• 输入格式：第一行三个整数 $n, S, T$，分别表示候选区间数、目标区间的起点与终点。接下来 $n$ 行，每行两个整数 $l_i, r_i$。
• 输出格式：一个整数，表示最少所需区间数；若无法完全覆盖输出 -1。
• 数据范围：$1 \le n \le 2\times 10^5$，$-10^9 \le S < T \le 10^9$，$-10^9 \le l_i \le r_i \le 10^9$。

样例 1

输入

5 1 10
1 3
2 6
5 8
7 11
8 12

输出

4

// 最少区间覆盖
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;

struct Seg{
	int l,r;
}a[N];

bool cmp(const Seg& x,const Seg& y){
	return x.l<y.l;
}

void solve(){
	int n,S,T;
	if(!(cin>>n>>S>>T)) return;
	for(int i=1;i<=n;i++){
		cin>>a[i].l>>a[i].r;
	}
	
	// 1. 按左端点从小到大排序
	sort(a+1,a+1+n,cmp);
	
	int ans=0;
	int cur=S;
	int i=1;
	bool ok=false;
	
	// 2. 双指针向右扫描
	while(i<=n){
		int max_r=-2e18;
		// 寻找所有能紧接当前覆盖边界 cur 的区间，找出延伸最远者
		while(i<=n && a[i].l<=cur){
			max_r=max(max_r,a[i].r);
			i++;
		}
		
		// 无法向右推进任何距离，说明发生断层
		if(max_r<=cur) break;
		
		ans++;
		cur=max_r;
		if(cur>=T){
			ok=true;
			break;
		}
	}
	
	if(ok) cout<<ans<<'\n';
	else cout<<-1<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

2. 区间最少分组问题：会场安排与堆的联手

如果考题不再允许我们“挑一部分、扔一部分”，而是要求所有活动一个都不能少，全部都要排进日程，但同一间教室在同一时刻依然只能容纳一场活动：

问题模型：给定 $n$ 个活动区间 $[l_i, r_i)$（左闭右开），求最少需要开辟多少间教室，才能把所有活动全部安排妥当且互不冲突？

贪心策略：按开始时间流推进，小根堆实时找空闲

很多同学在思考“最少分组”时，下意识想穷举每间教室能塞谁，这很容易滑向搜索。 其实换一个现实物理视角：活动是按照时间先后来到的，我们只要在每个活动进场时，优先把它塞进一间已经下课的空闲教室即可。

1. 排序基准：按活动开始时间 $l_i$ 从小到大升序排序。
2. 堆的物理意义： 建立一个小根堆 priority_queue<int, vector<int>, greater<int>> q;。 堆中存放的是每间已开教室当前的“下课时间”（即占用截止时间）。 因此，堆顶元素 q.top() 代表全场最早能腾出空位的教室！
3. 决策逻辑： 对于当前到来的活动 $a[i]$：
   • 检查堆顶：若 q.top() <= a[i].l，说明全场最早下课的教室此时已经空出来了！那么当前活动直接进驻这间教室即可。我们弹出旧的下课时间，将该教室的新下课时间 $a[i].r$ 压入堆中。
   • 若 q.empty() 或 q.top() > a[i].l，说明连最早下课的教室都还在上课，全场所有已开教室统统处于占用状态！没有任何旧教室能收纳它，我们只能新开一间教室，直接把 $a[i].r$ 压入堆中。
4. 最终结果： 所有活动扫描完毕后，堆中元素的总个数 q.size()，正是我们最终开辟的最少教室数量。

模拟手推：堆的动态伸缩

4 个活动 $[1, 4), [2, 5), [4, 7), [6, 9)$：

1. 考察 $[1, 4)$：堆为空，新开第 1 间教室，压入下课时间 4。堆为 $\{4\}$。
2. 考察 $[2, 5)$：堆顶 $4 > 2$，尚未下课，冲突！新开第 2 间教室，压入 5。堆为 $\{4, 5\}$。
3. 考察 $[4, 7)$：堆顶 $4 \le 4$，第 1 间教室下课！复用它：弹出 4，压入 7。堆为 $\{5, 7\}$。
4. 考察 $[6, 9)$：堆顶 $5 \le 6$，第 2 间教室下课！复用它：弹出 5，压入 9。堆为 $\{7, 9\}$。 最终堆的大小为 2，最少只需 2 间教室。

实战标程：最少教室安排

输入输出协议与数据范围

• 输入格式：第一行一个整数 $n$。接下来 $n$ 行，每行两个整数 $l_i, r_i$。
• 输出格式：一个整数，表示最少所需教室数。
• 数据范围：$1 \le n \le 2\times 10^5$，$0 \le l_i < r_i \le 10^9$。

样例 1

输入

4
1 4
2 5
4 7
6 9

输出

2

// 最少教室安排
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;

struct Seg{
	int l,r;
}a[N];

bool cmp(const Seg& x,const Seg& y){
	if(x.l!=y.l) return x.l<y.l;
	return x.r<y.r;
}

void solve(){
	int n;
	if(!(cin>>n)) return;
	for(int i=1;i<=n;i++){
		cin>>a[i].l>>a[i].r;
	}
	
	// 按开始时间升序排序
	sort(a+1,a+1+n,cmp);
	
	// 小根堆记录每间教室的结束时间
	priority_queue<int,vector<int>,greater<int>> q;
	
	for(int i=1;i<=n;i++){
		// 若最早下课的教室已空闲，复用它
		if(!q.empty() && q.top()<=a[i].l){
			q.pop();
		}
		// 压入当前教室新的下课时间
		q.push(a[i].r);
	}
	
	cout<<q.size()<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

八、堆的动态维护进阶：Top K 过滤与双堆对顶

在上一节的区间分组中，堆悄悄扮演了“最快空闲资源管理者”的角色。除了用于合并果子和分配资源，堆在竞赛中更普遍的看家本领，是对海量数据流进行实时极值过滤与动态分位数维护。

1. 动态 Top K 过滤：为什么找前 K 大要建小根堆？

问题模型：在数据规模极其庞大（例如 $n = 10^7$），内存根本开不下大数组保存全部元素时，如何在线流式维护并最终输出前 $k$ 大的所有数？

直觉误区：

初学者第一直觉往往是：“求最大，我建大根堆啊！” 如果大根堆只维护 $k$ 个元素，堆顶是这 $k$ 个数里的最大值。当数据流来了一个新数 $x$ 时，堆顶这个“全场第一”根本无法回答你：“新数 $x$ 究竟有没有资格把当前前 $k$ 名里垫底的那个人挤下去？”

破局机制：小根堆充当“门槛守门员”

求前 $k$ 大，必须使用容量为 $k$ 的小根堆！

• 堆的物理意义：堆中始终容纳当前见过的“最强 $k$ 人候选团”。
• 堆顶的物理意义：它是这 $k$ 个人里面最弱的一个（守门员）。
• 流式决策：
  1. 堆中元素不足 $k$ 个时：新数无条件直接入堆；
  2. 堆中元素已满 $k$ 个时：
     • 若新数 $x > q.top()$：说明新数超越了守门员门槛，守门员被当场踢出（q.pop()），新数晋级入选（q.push(x)）；
     • 若新数 $x \le q.top()$：说明连守门员都打不过，直接无视丢弃。

这样，算法的空间复杂度严格被压制在 $O(k)$，处理每个新数仅耗时 $O(\log k)$，总时间仅为 $O(n \log k)$。

模拟手推：门槛是怎样被逐步抬高的？

求前 $3$ 大（$k = 3$），数据依次到来：$5, 2, 8, 3, 9, 1, 7$。

1. 进 $5$：堆 $\{5\}$
2. 进 $2$：堆 $\{2, 5\}$
3. 进 $8$：堆 $\{2, 5, 8\}$（满 $3$ 个，当前门槛守门员为 2）
4. 进 $3$：$3 > 2$，弹出 2，压入 3。堆变为 $\{3, 5, 8\}$（门槛抬高到 3）
5. 进 $9$：$9 > 3$，弹出 3，压入 9。堆变为 $\{5, 8, 9\}$（门槛抬高到 5）
6. 进 $1$：$1 \le 5$，淘汰。堆保持 $\{5, 8, 9\}$
7. 进 $7$：$7 > 5$，弹出 5，压入 7。堆变为 $\{7, 8, 9\}$（门槛抬高到 7） 最终留在堆中的正是全场前 3 大：$7, 8, 9$。

实战标程：数据流 Top K 筛选

输入输出协议与数据范围

• 输入格式：第一行两个整数 $n, k$。第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。
• 输出格式：一行 $k$ 个整数，按从小到大升序输出最终的前 $k$ 大数值。
• 数据范围：$1 \le k \le n \le 2\times 10^5$，$1 \le a_i \le 10^9$。

样例 1

输入

7 3
5 2 8 3 9 1 7

输出

7 8 9

// 数据流 Top K 筛选
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
	int n,k;
	if(!(cin>>n>>k)) return;
	
	// 容量为 k 的小根堆作为门槛淘汰器
	priority_queue<int,vector<int>,greater<int>> q;
	
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		if((int)q.size()<k){
			q.push(x);
		}else if(x>q.top()){
			q.pop();
			q.push(x);
		}
	}
	
	// 依次取出堆顶，天然为升序排列
	vector<int> ans;
	while(!q.empty()){
		ans.push_back(q.top());
		q.pop();
	}
	
	for(int i=0;i<(int)ans.size();i++){
		cout<<ans[i]<<(i+1==(int)ans.size()?'\n':' ');
	}
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

2. 对顶堆：动态维护中位数与第 K 小（选学）

先修说明：本节为竞赛进阶技巧。要求已掌握单堆基本操作与二叉堆结构。若当前重点在基础贪心调度，可先通读思路，待遇上动态分位数题型时再深入实现。

在 Top K 模型中，堆的大小是固定的 $k$，守门员单向把关。但如果题目要求随着数据不断插入，随时以 $O(1)$ 查出当前所有已插入元素的中位数，单个堆就力不从心了。

物理机制：两个堆背靠背的“天平”

我们将所有数据按大小切成两半，用两个堆“对顶”拼接：

• 大根堆 left_heap：维护较小的那一半数据；
• 小根堆 right_heap：维护较大的那一半数据。

[较小的一半 (大根堆 left_heap)]  <-- 堆顶 left.top() | 对顶接缝 | right.top() -->  [较大的一半 (小根堆 right_heap)]

双堆平衡约束

为了让中位数始终稳坐堆顶，我们维持两项铁律：

1. 数值分界：随时保证 left_heap.top() <= right_heap.top()；
2. 数量均摊：始终保证 left_heap.size() == right_heap.size() 或 left_heap.size() == right_heap.size() + 1。

当新数插入时，先根据与 left_heap.top() 的大小关系放入对应堆中，随后通过 left_heap 与 right_heap 之间的单向弹出与压入，重新平衡两侧数量。此时，大根堆的堆顶 left_heap.top() 就是动态中位数（偶数个元素时，取较小的那个中间值）。

// 核心平衡逻辑片段（依赖全局或类内双堆）：
priority_queue<int> left_heap;                             // 大根堆维护较小半区
priority_queue<int, vector<int>, greater<int>> right_heap; // 小根堆维护较大半区

void insert(int x){
	if(left_heap.empty() || x<=left_heap.top()) left_heap.push(x);
	else right_heap.push(x);
	
	// 动态微调两侧天平平衡
	if((int)left_heap.size() > (int)right_heap.size()+1){
		right_heap.push(left_heap.top());
		left_heap.pop();
	}else if((int)left_heap.size() < (int)right_heap.size()){
		left_heap.push(right_heap.top());
		right_heap.pop();
	}
}

int get_median(){
	return left_heap.top();
}

九、进阶思维跨越：从堆合并到反悔贪心

把 Top K 中“新来的更好，就替换堆顶”的思路用来撤销已选决策，我们就走到了反悔贪心的门口。

很多同学在刷题时容易产生一种思维惯性：“只要这道贪心题用了小根堆，它的逻辑就和合并果子差不多。” 这是非常危险的误解！在信奥高阶贪心中，堆有着两种截然不同的物理角色：

单位耗时任务如何按截止日期筛选、收益更高时怎样反悔，见《反悔贪心》第二节；本讲先分清两种堆的角色。

在敲下 priority_queue 之前，必须先在脑海中审视：你的堆顶，到底是在等待合成的材料，还是随时准备替罪的弃子？

十、渐进式实战练习题单

第一阶段：方案输出与记录

1. 活动安排方案重构
   • 题目要求：基于【实战标程一】，数据给出 $n$ 个活动。第一行输出最多能安排的活动场次；第二行输出一个按时间先后排列的可行活动编号序列（编号为 $1 \sim n$，按输入原始顺序编号）。若有多组可行序列，输出任意一组即可。
   • 破题引导：在 Seg 结构体中绑定原始编号 id。在贪心选择时，千万不要在扫描原数组时直接输出，只有当条件 !chosen || a[i].l >= last 真正成立、判定入选时，才将 a[i].id 压入答案容器中。

第二阶段：模型数学微扰 2. 带固定开销的材料合成

• 题目要求：基于【实战标程二】，每次合成操作除了支付两堆材料的重量和之外，还需要额外支付一笔固定的手续费 $C$（$0 \le C \le 10^6$）。求将 $n$ 堆材料合成一堆的最小总费用。
• 破题引导：仔细思考：无论你按照什么顺序合并，将 $n$ 堆合成 1 堆，总共必须且只能发生多少次合并操作？每一次合并操作都会产生一个固定且不可避免的 $+C$。这个额外的固定常数会不会改变最优树形结构的权值分布？直接利用纯数学推导，看看贪心代码到底需不需要为 $C$ 改变堆的排序规则。

第三阶段：反例构造与证明攻防 3. 致命反例构造

• 题目要求：请分别针对以下两种错误的直觉贪心规则，各构造一组数据量不超过 4 的极简反例，并手推列出错误规则跑出的结果与真正最优解的结果：
  • 规则甲（区间调度）：每次优先选持续时间最短的活动。
  • 规则乙（材料合成）：每次优先合并当前重量最大的两堆材料。
• 破题引导：反例必须给出具体区间和具体数值，算出确凿的答案差距，彻底封死逻辑漏洞。此外，尝试给区间调度问题的每个活动增加一个权值 $v_i$，从微扰交换的角度写下一段简短推导，阐明原有的“结束时间最早”为什么无法在带权场景下保持正确性。