贪心算法专题-课时1
贪心算法专题课时1:排队接水、区间调度、最大子段和,以及贪心决策模型、国王游戏与序贪心条件。
-
单独打开
按接水时间升序,时间相同按编号升序。
- 总等待时间为 ,相邻交换证明排序最优。
- 输出排队顺序和平均等待时间。
-
单独打开
按右端点升序扫描,能与上一个选中区间相容就选。
- 右端点最小的选择可以用交换论证证明安全。
- 每个区间只需判断左端点是否不小于当前右端点。
- 这是静态全序贪心的最小例题。
-
单独打开
求数组中和最大的连续非空子段。
- 固定右端点时,前缀和减去此前最小前缀和。
- Kadane 递推 ;全负序列要初始化负无穷。
-
单独打开
把贪心写成状态、动作、代价与安全选择:每步选择的动作 必须与某个最优续篇一致。
- 交换论证负责证明局部选择能扩展成全局最优。
- 拟阵只是选择型的一类充分结构,不是贪心的必要条件。
- 与 DP 的分界:贪心只保留一条决策路径,DP 保留一族最优值。
-
单独打开
把大臣按 升序排列。
- 相邻两人的奖励最大值比较给出交换依据。
- 前缀乘积和答案超过 64 位,需要高精度。
-
单独打开
候选带优先级,每步取当前优先级最高的动作。
- 静态全序:用相邻交换证明排序后不劣。
- 后继关系:若后继键不小于父键,当前最小键就是安全选择。
- 重点检查优先级是否随状态变化,以及后继键单调性是否成立。
当前内容
知识点内容
点击左侧条目查看内容。