贪心算法专题-课余

未授课内容

24 个条目 · 点击条目切换内容

下载讲义 PDF
  1. 行、列建点,卡片建边。

    • 可行选择等价于边集可定向且每个端点入度不超过 1,即伪森林。
    • 伪森林是双循环拟阵的独立集;按边权降序做拟阵贪心。
    • 带环标记的并查集判断加入后是否会出现两个环。
    单独打开
  2. 每次合并当前最小的两个元素,支付两者之和。

    • 合并树的总代价等于叶权乘深度之和;交换最深兄弟可证明最优。
    • 若合并代价不是两权之和,或一次合并不止两个元素,最小两个规则不自动成立。
    • 块合并问题仍可沿用合并树的交换论证,只是比较键变成块的统计量。
    单独打开
  3. 块记录其中 0 与 1 的个数,按 𝐵0/𝐵1 从大到小合并。

    • 取比例最大的非根块并入父块,跨块只增加 𝐴1𝐵0 个逆序对。
    • 优先队列维护比值,并查集定位当前父块。
    • 交换论证说明把最优块前移不劣;这是合并型贪心的树形变体。
    单独打开
  4. 先接受当前元素,不可行时删除或替换已选元素。

    • 用堆、链表或残余网络维护反悔项,比较新代价与最大可省代价。
    • 关键仍是安全选择:替换后的集合必须能扩展成某个最优解。
    • 一次替换可能不足以恢复可行,需要多步增广或更复杂的交换结构。
    单独打开
  5. 按截止时间处理任务,超时后删除加工时间最长的任务。

    • 原问题等价于选择最大的可行准时任务集合。
    • 正确性来自交换论证,不依赖拟阵;一般加工时间下可准时集合不是拟阵。
    • 这是反悔贪心在调度问题中的标准入口。
    单独打开
  6. 按结束时间排序,把任务分给结束时间最晚且不冲突的学生。

    • Best Fit EFT:在所有可接学生中选结束时间最大的一个。
    • 用 multiset 维护学生结束时间,查询前驱。
    单独打开
  7. 选择不重叠区间,使总权值最大。

    • 按右端点排序,𝑝𝑖 为右端点不超过 𝑙𝑖 的最大前驱。
    • 𝑓𝑖=max(𝑓𝑖−1,𝑤𝑖+𝑓𝑝𝑖)。
    单独打开
  8. 把带权区间分配到 𝑚 台机器,使总权值最大。

    • 时间链边容量 𝑚、费用 0;区间边容量 1、费用 −𝑤𝑖。
    • 跑流量为 𝑚 的最小费用流。
    单独打开
  9. 所有区间都要安排,求最少机器数。

    • 按左端点排序,用小根堆维护机器结束时间。
    • 答案等于最大重叠深度。
    单独打开
  10. 用最少区间覆盖目标区间。

    • 按左端点排序,维护当前覆盖到的右端点。
    • 每次在能接上的区间中选右端点最远者。
    单独打开
  11. 用最少点使每个区间至少包含一个点。

    • 按右端点排序。
    • 遇到未覆盖区间时,在它的右端点放点。
    单独打开
  12. 维护所有可达余额的区间 [𝐿,𝑅]。

    • 非检查日整体平移;上界溢出时压低之前的存款。
    • 检查日只有 𝑅<0 时才强制存款,之后区间重置为 [0,𝑑]。
    • 只在检查日调整,避免无意义的存款次数。
    单独打开
  13. 一次移动等价于修改一个前缀和。

    • 固定 𝑘 后,每个前缀和独立取最近的 𝑘 的倍数。
    • 总代价为 ∑min(𝑟𝑖,𝑘−𝑟𝑖);只需枚举总糖果数的质因子。
    • 合数 𝑘 的代价不小于其质因子的代价,因此枚举质因子即可。
    单独打开
  14. 最优答案单调不降,且由若干段平均值组成。

    • 前缀和点的下凸壳给出最优分段。
    • 单调栈合并相邻逆序段;交叉相乘避免浮点误差。
    • 每个段只进出栈一次,时间是线性的。
    单独打开
  15. 支持区间覆盖,查询区间内至多 𝑘 个不相交子段的最大和。

    • 线段树维护最大/最小前后缀、子段和及其端点。
    • 每次取最大子段并取反,再重复;最后撤销取反。𝑘≤20。
    单独打开
  16. 把隐式状态空间组织成每个非根状态恰有一个父状态的树。

    • 父值不大于子值,堆按值弹出即为非降序。
    • 唯一父状态保证不重不漏;每个状态只生成常数个后继。
    • 它是序贪心条件中后继关系的特例,适合第 𝑘 小枚举。
    单独打开
  17. 正数序列的子集和,以空集为根。

    • 每个状态只生成“末尾下标加一”和“追加下一下标”两个后继。
    • 排序后父值不大于子值,直接套用唯一父状态堆枚举。
    • 重复值按不同下标子集分别计数。
    单独打开
  18. 每个集合选一个数,求第 𝑘 小的和。

    • 按首增量 𝑑𝑖=𝐴𝑖,2−𝐴𝑖,1 排序,状态压缩为最近一个非首项。
    • 三种后继:推进当前集合、切换到下一个集合、撤销当前集合的第一次增量。
    • 第三种是反悔转移,排序保证三种转移都不减小价值。
    单独打开
  19. 树上选最少的消防站,使每个点距离不超过 2。

    • 按深度从大到小,找未覆盖点的爷爷建站。
    • 每次标记距离不超过 2 的点。
    单独打开
  20. 按数值从小到大尝试选格,维护每行可选列区间。

    • 选中 (𝑟,𝑐) 后,上方行的右端点压到 𝑐,下方行的左端点抬到 𝑐。
    • 直到选出 𝑁+𝑀−1 个数。
    单独打开
  21. 在加减表达式中加括号,使结果最大。

    • 只有减号后的括号有意义,嵌套最多两层。
    • 用括号外、奇数层、偶数层三个状态做 DP。
    单独打开
  22. 构造长度为 𝑁2 的序列,满足每个数出现 𝑁 次及第 𝑖 个 𝑖 的位置。

    • 先按 𝑥𝑖 升序,从左往右填每个数左侧需要的个数。
    • 再按 𝑥𝑖 降序,从右往左填右侧需要的个数。
    单独打开
  23. 面值为 2 的幂,询问凑出 𝑥 的最少硬币数。

    • 统计每个二进制位的硬币数量。
    • 从高位到低位尽量取,无法继续则无解。
    单独打开
  24. 把 2𝑁 个数配对,最小化 (𝑥+𝑦)mod𝑀 的最大值。

    • 排序后存在一个分界点,两段内部首尾配对。
    • 二分最小合法分界点,分别取两段最大值。
    单独打开
当前内容

知识点内容

点击左侧条目查看内容。

源码位置