# 练习 ## 经典题目 ### CF 1800C2 贪心，对于每个整数 $0$，选取之前还未被删除的最大正整数并删除。 ### CF 1579D 本题的“配对模型”是一个经典的模型，需要牢记原理。 贪心策略为每次选择两个最大的正整数并减去 $1$。 贪心证明参考[CF 1579D 证明（官方和 chatgpt 概括证明）](CF%201579D%20证明（官方和%20chatgpt%20概括证明）.md)（反证法）和[CF 1579D 证明（我的证明）](CF%201579D%20证明（我的证明）.md)（数学归纳法）。 也可以一大一小配对。 ### CSES 1164 贪心+小根堆。 - 维护一个小根堆 `pq`，元素（状态）是 `(该房间最后一位顾客的退房日, 房间号)`。 - 将顾客按到达日 $a$ 升序排序（到达日相同的顾客顺序随便）。按顺序处理当前顾客 $(a,b)$： - 若堆中退房日最早的房间的退房日 $\lt a$，说明存在房间可复用（至少堆顶这个可复用），弹出堆顶并把该房间分给当前顾客，再把 `(b, 房间号)` 压回堆； - 否则开新房间，房间数 `rooms++`，分配给当前顾客，并压入 `(b, rooms)`。 实际上将本贪心策略改为选取任意一个退房日 $\lt a$ 的房间都是可以，具体证明请参考 [区间分组](区间分组.md)。 ### 洛谷 P1631 序列合并 堆优化。经典模型。 如果暴力记录所有和，再加上排序，时间复杂度高达 $O(n^2 \log n)$。 我们可以先对 $n^2$ 个和进行分组： * 第一组：$a_1 + b_1, a_1 + b_2, a_1 + b_3, \dots, a_1 + b_n$ * 第二组：$a_2 + b_1, a_2 + b_2, a_2 + b_3, \dots, a_2 + b_n$ * $\dots$ * 第 $n$ 组：$a_n + b_1, a_n + b_2, a_n + b_3, \dots, a_n + b_n$ 由于题目给出的序列 $a$ 和 $b$ 都是单调不减的，我们发现每组内的 $n$ 个和也都是单调不减的。 思想：可以对每一组维护最小值，然后找到 $n$ 个组的最小值，找到后，将该组的最小值更新。 暴力用 $n$ 个指针维护每一组的最小值，每次取一个最小值 $O(n)$，总时间 $O(n^2)$。 设计状态【和，和所属的组，和在所属组中是第几个】。一开始先将每组的最小和的状态存储在堆中。每次取出堆中的最小和后，将该组的后一个和压入到堆中。执行 $n$ 次这样的操作，最小的 $n$ 个和就得到了。总时间 $O(n \log n)$。 为了方便实现，使用结构体表示状态，使用 priority_queue 代替堆。 扩展：$n \times n$ 的数字矩阵中，每行取一个数字得到数字和，求前 $n$ 小数字和。 ### 洛谷 P4053 建筑抢修 反悔贪心。贪心题目基本上是通过大量刷题攒经验和玄学构造来解决的，少数同学能用天赋加速大量刷题的过程。贪心的证明亦如此。 这个题状态有两个属性【修理时长，截止时刻】，可以先对截止时刻排序（相当于是给所有建筑定义了一个优先级，截止时间越早的肯定越要先完成）。 按排序后的顺序模拟修理建筑，并记录修理总时长。反例如下： ``` 3 100 100 2 101 3 102 按此贪心只能修第 1 个建筑，实际能修第 2、3 个 建筑 ``` 如果总时长不超过当前建筑的截止时刻，那就把当前建筑加入到修理计划当中； 否则，说明必然有一个建筑是不能修理的（如何理解？），为了让后面的建筑修理有更多的时间，我们应该不去修理前面所有建筑中时长最长的那一个（如何理解？）。 可以用堆来存储所有修理建筑的时长，加入修理计划——堆中插入元素，移除时长最长的建筑——删除堆中最大值。 ## 前 K 大问题 ### abc234_d 我们可以使用优先队列动态地维护一个序列的前 $K$ 大元素。 假设 $A_1, A_2, \dots, A_i$ 中的前 $K$ 大元素用一个容器存储了下来。当加入 $A_{i + 1}$ 时，有两种情况： - 如果 $A_{i + 1}$ 比容器中最小的元素还要小，则 $A_1, \dots, A_{i + 1}$ 的前 $K$ 大就是该容器存储的元素。 - 否则，删掉容器中的最小元素，并往容器中加入 $A_{i + 1}$，得到 $A_1, \dots, A_{i + 1}$ 中的前 $K$ 大。 实际上，操作可以简化为，把 $A_{i + 1}$ 扔进容器，然后删除容器中的最小元素。使用优先队列可以在 $O(\log K)$ 的时间内维护。 （需要示意图） ### 对顶堆（双堆维护分界线） 对顶堆。用两个相反的堆来对所有元素按值域进行划分。 我们可以设置两个堆，一个大根堆存储较小部分的所有元素，一个小根堆存储较大部分的所有元素。例如当前已有一个排序好的序列 $[A_1, A_2, A_3, A_4, A_5]$，那大根堆中存储 $[A_1, A_2, A_3]$，小根堆中存储 $[A_4, A_5]$。 我们发现： * 堆的大小就是分界线的位置 * 堆顶元素就是分界线两端的元素 * 将一个堆顶元素移动到另一个堆中，就是调整分界线 （需要示意图） ### 洛谷 P1168 动态中位数 核心技术点： 1. 使用两个相反的堆对元素按大小进行分类 2. 将中位数记录在较小元素的大根堆堆顶中 3. 在插入元素后，及时调整分界线；每插入一次，分界线最多移动一次 那么我们在插入元素时，可以根据该元素与两个堆顶的大小来决定他所应该插入的堆（仔细思考插入过程）。在查询中位数时，通过移动堆顶元素（如何移动？）调整分界线的位置，使得大根堆存储的元素数量为 $\left \lceil \dfrac{N}{2} \right \rceil$（$N$ 为当前已插入的元素数量），此时大根堆的堆顶恰好就是中位数。 对于此题，可以每次插入元素时，就调整分界线的位置。可以证明每次分界线最多移动一个单位。 插入元素总时间 $O(n \log n)$，移动分界线总时间 $O(n \log n)$（为什么最多移动 $n$ 次？需要示意图） 由于只需要存储值，使用 priority_queue 来实现。 ## 哈夫曼树 [哈夫曼树](哈夫曼树.md) ## 其他习题 ### 简单习题 [CSP-J2020 直播获奖](https://www.luogu.com.cn/problem/P7072) 对顶堆 [P1801 黑匣子](https://www.luogu.com.cn/problem/P1801) 对顶堆 [P2949 Work Scheduling](https://www.luogu.com.cn/problem/P2949) 反悔贪心 [P7913 廊桥分配](https://www.luogu.com.cn/problem/P7913) ### [洛谷 P2278 操作系统](https://www.luogu.com.cn/problem/P2278) 注意：当一个进程 $p$ 还在运行（未结束时），如果来了一个优先级更高的进程 $q$，保留 $p$ 的进度，然后进行 $q$。 枚举每个到来的进程 $i$： - 先执行完等待队列中不被 $i$ 干扰的进程。 - 如果还剩进程（会被干扰的），令接下来要执行的是进程 $j$，比较 $j$ 和 $i$ 的优先级 $p_j, p_i$ - $p_j \ge p_i$，执行 $j$，进程 $i$ 在等待队列中 - $p_j \lt p_i$，执行 $j$ 的一部分直到 $i$ 到来，然后执行 $i$。$i$ 后续是否有优先级更大的进程未知。 将所有进程按照以上步骤加入等待队列后，如果队列中还剩进程，模拟执行。用优先队列维护等待队列，记录每条进程的编号、到达时间、优先级、**剩余**执行时间。 ### [最小函数值](https://www.luogu.com.cn/problem/P2085) $\mathbb N*$ 是正整数集。根据一些初中代数知识可知，$F_1(x) \sim F_n(x)$ 在 $x \in [1, \infty)$ 上单调递增。类似于最大和，我们将 $F_1(1) \sim F_n(1)$ 存入优先队列中，每次弹出最小值 $F_t(x)$ 后将该函数的下一个值 $F_t(x + 1)$ 压入优先队列，操作 $m$ 次即可。时间复杂度 $O(m \log n)$。 ### [洛谷 P2827 蚯蚓](https://www.luogu.com.cn/problem/P2827) 本题先考虑暴力模拟，维护一个蚯蚓列表，每次在列表中查找蚯蚓长度最大值，切半，然后给其他所有蚯蚓长度 $+q$。时间复杂度 $O(m(n+m))$。 所使用到的查找、切半操作可以使用手写堆或优先队列维护，其他所有蚯蚓长度 $+q$，从相对的视角来看是给分出两个蚯蚓的长度 $-q$。这样单次操作能以 $O(\log (n+m))$ 的时间维护。注意切半时需要先还原为原长度。 对于满分做法，有一个结论是先切半分出的蚯蚓长度 $a, b$ 一定比后切半分出的蚯蚓的长度 $c, d$ 长，即 $a \gt c, b \gt d$，因此可以用三个队列分别存储原来的 $n$ 只蚯蚓（从大到小排好）、切半 $\lfloor px \rfloor$ 的蚯蚓、切半 $x - \lfloor px \rfloor$ 的蚯蚓，每次在三个队头寻找最大值，切半后的蚯蚓放在相应队尾即可。 ### [洛谷 P3045 Cow Coupons](https://www.luogu.com.cn/problem/P3045) 贪心策略为选择 $C_i$ 小的奶牛用完优惠券（花钱尽可能少），然后剩下奶牛直接购买。这个贪心显然是错的。 假设存在一个直接购买的奶牛 $j$，买完 $j$ 之后的价格 $x \le M$。如果用优惠券买 $j$，意味着用优惠券购买的奶牛集合中有一头要直接购买，令其为 $i$，此时花费 $x - P_j + C_j - C_i + P_i = x + (P_i - C_i) - (P_j - C_j)$。 令 $D_i = P_i - C_i$ 表示使用优惠券可以优惠的钱数，如果 $D_i \lt D_j$，$x + (P_i - C_i) - (P_j - C_j) = x + D_i - D_j \lt x$，所有后面的奶牛中有可能存在用优惠券买的。 贪心调整为，先选择 $C_i$ 小的 $K$ 个奶牛用优惠券，对于剩余的奶牛 $K + 1 \sim N$ 找直接购买花费最少的奶牛 $x$（$P_x$ 最小的）和用优惠券购买花费最少的奶牛 $y$（$C_y$ 最小的），然后选择其中花费最少的情况处理。注意延迟删除的问题。