贪心方法

· · 个人记录

2025.8.21

临项交换法

适用于将序列重排列使最优的题目。 当不知道最优序列满足什么性质时，可以使用这个方法。

例：P1080 [NOIP 2012 提高组] 国王游戏

2025.8.24 upd:[AGC023F] 01 on Tree

首先，是最优排列顺序。

容易发现，在 suma_1 \times sumb_0 < sumb_1 \times suma_0 时，排列最优。注意这就可以直接排序了！！！。当然，不放心也可以移项，将一个点的变量放在一边，变成一个除法的形式。

文章：

1

2

线段覆盖/选最多的线段（P2255 [USACO14JAN] Recording the Moolympics S）

可以考虑按右端点排序，能放就尽量放。

注意贪心最小化/最大化的是什么

哈夫曼树的构建

构建 k 叉哈夫曼树：

  1. 所有叶子节点对应着一个字符串，权值为出现次数。

  2. 每次选择权值前 k 小的 k 个节点，合并在一起，压入优先队列

  3. 注意可能节点放不满导致不优，加入一些权值为 0 的节点直到 (n-1)%(k-1)=0 时就可以了。（为什么是这个式子：因为每一次合并会减少 k-1 个节点，最后只剩 1 个节点，减少 n-1 个节点，每一轮保证有 k 个节点，所以 n-1 是 k-1 的倍数）

题：P2168 [NOI2015] 荷马史诗

完全图定向

首先，一个拓扑序唯一对应一个 DAG 竞赛图（有向完全图）。

根据拓扑序的定义，这个点只会向拓扑序在它后面的点连边，所以出度是 n-1 到 0。

这样P8896 「DPOI-1」道路规划的出度限制条件就可以转化为序列值的限制，然后就可以做了。

具体：将满足左端点限制的点全部压入优先队列，按右端点排序，每次将这个点放入右端点最小的那个区间。

贪心的定义

贪心是通过局部最优解得到全局最优解的方法。

所以有些题目应先考虑边界怎么做，即最小的情况，再合并。

如CF525D Arthur and Walls

一种反悔贪心（？）

CF3D Least Cost Bracket Sequence

这道题中，我们可以先将所有 ? 号全部填做 ) ,然后再不合法时将 ) 变为 (,并将贡献做对应的增减。

不清楚是否能推广。

CF1085E Vasya and Templates

贪心，尽量贴着下界。

首先，再没有冲突的情况下，一直填 l 对应，当冲突后，向前找到第一个可以调整的位置，将字典序加1，后面就可一不用管下界了，尽量小地填。

P4765 [CERC2014] The Imp

临项交换法的题目。

我们需要找出以个最优的选物品的顺序（最优策略）。考虑用邻项交换法来证明。

设有两个物品，是[v_1,c_1],[v_2,c_2]

最优排序有 \min(v_1-c_1,v_2-c_1-c_2) < \min(v_1-c_1-c_2,v_2-c_2)

分类讨论：

  1. v_1-c_1<v_2-c_2

    同时 v_1-c_1-c_2 > v_2-c_2

    所以 v_1-c_1-c_2>v_1-c_1

    不合法

  3. v_2-c_1-c_2 < v_1-c_1-c_2 \to v_2<v_1

所以按 v 从小到大来排列，然后进行DP

CF1685C Bring Balance

画图，证明上界，神秘结论题。

CF436E Cardboard Box

有反悔贪心做法，也可以对普通贪心魔改。

题解

CF1493E Enormous XOR

打表找规律