从零开始的算法复建
前言
高考之后，算法能力大幅退化，于是决定从零开始重建。本文记录了从零开始算法复建的过程。
贪心
贪心算法是大多数人最早接触的算法之一，但其内涵远比表面看来深刻。
基本思想
贪心的基本思想是：在 不对后续产生影响 的前提下，对当前子问题做出 局部最优选择。由于这一局部抉择不会对后续（全局）产生影响，因此所得的局部最优解能够构成全局最优解，即满足 最优子结构。
类型一：直接利用贪心选择性质
首先，我们需要明确“不对后续产生影响”的具体含义。
通常分为以下两种情况：
- 选择当前元素后，后续可选元素的集合不变（不影响后续选择的可行性）；
- 选择当前元素后，后续选择的最优解不受影响（不影响后续最优解的价值）。
第一种情况通常较为显然，此处不再赘述。重点分析第二种情况。
若当前步骤的某个选择在效果上 严格优于或等价于 其他所有选择，则该选择必然能导向最优解。区间选择问题就是一个典型的例子。
区间选择问题
给定一组区间，要求选出尽可能多的互不重叠区间。贪心策略：每次选择结束时间最早的区间。
证明思路：设最优解 \(O\) 的第一个区间为 \(I'\)，其结束时间不早于贪心选择的区间 \(I\)。将 \(O\) 中的第一个区间替换为 \(I\)——由于 \(I\) 结束更早，剩余空间更大，后续可选区间数不会减少，替换后依旧是最优解。反复替换，最终得到贪心解。这一证明的本质是：局部最优（最早结束）为后续留下了最大的自由度。
此类问题中，我们可以较为直观地得出某种选择严格优于其他选择，因此可以直接采用贪心策略。
类型二：序列排序型（调整法）
但对于有些问题，个别选择的优劣难以直接比较。此时需要通过 调整法 来证明贪心解的最优性。
例题：P1080 国王游戏
对此类序列排序问题，若单独讨论第 \(i\) 个元素的选择，其对后续的影响极大，难以直接比较。此时可以考虑 调整法。
每次选取相邻的两个位置，分别放置 \(a_i\) 和 \(a_j\)，通过比较交换前后价值的改变，得到使总价值增加的条件。依据此条件对序列进行排序，即可得到最优解。
为何调整法有效？其正确性可以从两个角度来理解：
正向建构：设想我们逐个确定每个位置的最优元素。假定最优元素不在最前面，我们通过不断交换相邻元素将它"冒泡"到当前位置，交换过程始终朝向价值增加的方向。最终每个位置都放着该处的最优元素——这与贪心的局部最优思想一脉相承。
反证法：若一个序列不满足上述排序条件，则必然存在相邻逆序对。交换这对元素即可得到更优解，与"当前为最优解"的假设矛盾。
需要注意：以上证明有一个默认前提——我们找到的排序条件必须满足 严格弱序性，即“小于”关系具有传递性，且“等于”关系同样具有传递性。只有满足这一前提，才能对序列进行正确排序。
一定要满足严格弱序性吗
更本质地说，我们只需要保证最终序列中所有元素对（不一定相邻）都满足排序条件即可。因此，如果比较条件本身不满足传递性，人为构造一套满足传递性的关系也是可行的。详见 P2123 皇后游戏。
由于只需考虑相邻元素的交换，证明难度远低于任意两个元素的交换，从而大幅简化问题。
类型三：反悔贪心
对于另一些问题，上面两种情况都不适用：我们无法找到一个选择使得保证能够在后续取到最优解。此时便需要引入 反悔贪心。
例题：P2949 [USACO09OPEN] Work Scheduling G
反悔贪心的核心思想是引入“补票”机制，允许在未来撤销已经做出的选择。
具体到本题，使用反悔贪心的关键在于：所有顾客的价值贡献 相同（均为 \(1\)，目标是最大化满足的顾客数）。这为反悔提供了可能——可以先尽量贪心地满足顾客，由于每位顾客的价值都是 \(1\)，后续的反悔不会影响总价值。在此基础上，剩余商品越多，越可能达到全局最优解。
重新审视题目，我们沿了是贪心思想：让剩余商品最多的选择尽量满足顾客。然而，局部最优并不保证全局最优——剩余商品最多的步骤未必能导向整体最优解。但由于本题中所有顾客的价值相同，引入反悔机制后，便可以让这种局部贪心导向全局最优解。