贪心算法专题-课余
未授课内容
-
单独打开
行、列建点,卡片建边。
- 可行选择等价于边集可定向且每个端点入度不超过 ,即伪森林。
- 伪森林是双循环拟阵的独立集;按边权降序做拟阵贪心。
- 带环标记的并查集判断加入后是否会出现两个环。
-
单独打开
每次合并当前最小的两个元素,支付两者之和。
- 合并树的总代价等于叶权乘深度之和;交换最深兄弟可证明最优。
- 若合并代价不是两权之和,或一次合并不止两个元素,最小两个规则不自动成立。
- 块合并问题仍可沿用合并树的交换论证,只是比较键变成块的统计量。
-
单独打开
块记录其中 与 的个数,按 从大到小合并。
- 取比例最大的非根块并入父块,跨块只增加 个逆序对。
- 优先队列维护比值,并查集定位当前父块。
- 交换论证说明把最优块前移不劣;这是合并型贪心的树形变体。
-
单独打开
先接受当前元素,不可行时删除或替换已选元素。
- 用堆、链表或残余网络维护反悔项,比较新代价与最大可省代价。
- 关键仍是安全选择:替换后的集合必须能扩展成某个最优解。
- 一次替换可能不足以恢复可行,需要多步增广或更复杂的交换结构。
-
单独打开
按截止时间处理任务,超时后删除加工时间最长的任务。
- 原问题等价于选择最大的可行准时任务集合。
- 正确性来自交换论证,不依赖拟阵;一般加工时间下可准时集合不是拟阵。
- 这是反悔贪心在调度问题中的标准入口。
-
单独打开
按结束时间排序,把任务分给结束时间最晚且不冲突的学生。
- Best Fit EFT:在所有可接学生中选结束时间最大的一个。
- 用
multiset维护学生结束时间,查询前驱。
-
单独打开
选择不重叠区间,使总权值最大。
- 按右端点排序, 为右端点不超过 的最大前驱。
- 。
-
单独打开
把带权区间分配到 台机器,使总权值最大。
- 时间链边容量 、费用 ;区间边容量 、费用 。
- 跑流量为 的最小费用流。
-
单独打开
所有区间都要安排,求最少机器数。
- 按左端点排序,用小根堆维护机器结束时间。
- 答案等于最大重叠深度。
-
单独打开
用最少区间覆盖目标区间。
- 按左端点排序,维护当前覆盖到的右端点。
- 每次在能接上的区间中选右端点最远者。
-
单独打开
用最少点使每个区间至少包含一个点。
- 按右端点排序。
- 遇到未覆盖区间时,在它的右端点放点。
-
单独打开
维护所有可达余额的区间 。
- 非检查日整体平移;上界溢出时压低之前的存款。
- 检查日只有 时才强制存款,之后区间重置为 。
- 只在检查日调整,避免无意义的存款次数。
-
单独打开
一次移动等价于修改一个前缀和。
- 固定 后,每个前缀和独立取最近的 的倍数。
- 总代价为 ;只需枚举总糖果数的质因子。
- 合数 的代价不小于其质因子的代价,因此枚举质因子即可。
-
单独打开
最优答案单调不降,且由若干段平均值组成。
- 前缀和点的下凸壳给出最优分段。
- 单调栈合并相邻逆序段;交叉相乘避免浮点误差。
- 每个段只进出栈一次,时间是线性的。
-
单独打开
支持区间覆盖,查询区间内至多 个不相交子段的最大和。
- 线段树维护最大/最小前后缀、子段和及其端点。
- 每次取最大子段并取反,再重复;最后撤销取反。。
-
单独打开
把隐式状态空间组织成每个非根状态恰有一个父状态的树。
- 父值不大于子值,堆按值弹出即为非降序。
- 唯一父状态保证不重不漏;每个状态只生成常数个后继。
- 它是序贪心条件中后继关系的特例,适合第 小枚举。
-
单独打开
正数序列的子集和,以空集为根。
- 每个状态只生成“末尾下标加一”和“追加下一下标”两个后继。
- 排序后父值不大于子值,直接套用唯一父状态堆枚举。
- 重复值按不同下标子集分别计数。
-
单独打开
每个集合选一个数,求第 小的和。
- 按首增量 排序,状态压缩为最近一个非首项。
- 三种后继:推进当前集合、切换到下一个集合、撤销当前集合的第一次增量。
- 第三种是反悔转移,排序保证三种转移都不减小价值。
-
单独打开
树上选最少的消防站,使每个点距离不超过 。
- 按深度从大到小,找未覆盖点的爷爷建站。
- 每次标记距离不超过 的点。
-
单独打开
按数值从小到大尝试选格,维护每行可选列区间。
- 选中 后,上方行的右端点压到 ,下方行的左端点抬到 。
- 直到选出 个数。
-
单独打开
在加减表达式中加括号,使结果最大。
- 只有减号后的括号有意义,嵌套最多两层。
- 用括号外、奇数层、偶数层三个状态做 DP。
-
单独打开
构造长度为 的序列,满足每个数出现 次及第 个 的位置。
- 先按 升序,从左往右填每个数左侧需要的个数。
- 再按 降序,从右往左填右侧需要的个数。
-
单独打开
面值为 的幂,询问凑出 的最少硬币数。
- 统计每个二进制位的硬币数量。
- 从高位到低位尽量取,无法继续则无解。
-
单独打开
把 个数配对,最小化 的最大值。
- 排序后存在一个分界点,两段内部首尾配对。
- 二分最小合法分界点,分别取两段最大值。
当前内容
知识点内容
点击左侧条目查看内容。