贪心算法专题-课时1

贪心算法专题课时1:排队接水、区间调度、最大子段和,以及贪心决策模型、国王游戏与序贪心条件。

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

下载讲义 PDF
  1. 按接水时间升序,时间相同按编号升序。

    • 总等待时间为 ∑(𝑛−𝑖)𝑇𝑝𝑖,相邻交换证明排序最优。
    • 输出排队顺序和平均等待时间。
    单独打开
  2. 按右端点升序扫描,能与上一个选中区间相容就选。

    • 右端点最小的选择可以用交换论证证明安全。
    • 每个区间只需判断左端点是否不小于当前右端点。
    • 这是静态全序贪心的最小例题。
    单独打开
  3. 求数组中和最大的连续非空子段。

    • 固定右端点时,前缀和减去此前最小前缀和。
    • Kadane 递推 𝑒𝑖=max(𝑎𝑖,𝑒𝑖−1+𝑎𝑖);全负序列要初始化负无穷。
    单独打开
  4. 把贪心写成状态、动作、代价与安全选择:每步选择的动作 𝑔(𝑠) 必须与某个最优续篇一致。

    • 交换论证负责证明局部选择能扩展成全局最优。
    • 拟阵只是选择型的一类充分结构,不是贪心的必要条件。
    • 与 DP 的分界:贪心只保留一条决策路径,DP 保留一族最优值。
    单独打开
  5. 把大臣按 𝑎𝑖𝑏𝑖 升序排列。

    • 相邻两人的奖励最大值比较给出交换依据。
    • 前缀乘积和答案超过 64 位,需要高精度。
    单独打开
  6. 候选带优先级,每步取当前优先级最高的动作。

    • 静态全序:用相邻交换证明排序后不劣。
    • 后继关系:若后继键不小于父键,当前最小键就是安全选择。
    • 重点检查优先级是否随状态变化,以及后继键单调性是否成立。
    单独打开
当前内容

知识点内容

点击左侧条目查看内容。

源码位置