贪心

贪心算法适用于解决无后效性（或者可以证明后效性不会使方案更劣）、具有最优子问题结构（一个问题的最优解包含其子问题的最优解）的问题。

贪心算法和 DP 的思想有点相近。

不同的是，DP 会列举所有可能成为最优解的解，然后比较后得到最优解（状态转移）。DP 的时间复杂度往往比较大，多数为 $O(n^2)$，也有少数的 $O(n)$ 线性 DP；贪心算法会按照一定的策略选择最优解，不需要统计每种可能，复杂度较小，往往在 $O(n)$。

证明贪心法正确常用的方法：

• 归纳法： 分类讨论，证明每种情况下贪心都正确。

• 反证法： 假设有更优解，证明更优解不存在。

• 调整法： 从贪心得到的解出发，做一些微调（例如交换 $i,j$），证明调整后都不会更优（当前方案不比调整后更劣）。

• 公式法： 推式子（一般是不等式），没什么好说的。

下面会介绍一些经典的贪心题。

加工生产调度（Johnson 法则，排序类贪心）

见：P1248 加工生产调度；题目大意如下：

有 $n$ 个产品需要生产，每个产品要在 $A,B$ 两个车间依次加工（必须先在 $A$ 车间加工），而且只有 $A$ 车间完成加工的产品送到 $B$ 车间后，$A$ 车间才能加工下一个产品。第 $i$ 个产品需要在 $A$ 车间加工 $A_i$ 单位时间，需要在 $B$ 车间加工 $B_i$ 单位时间。

现在需要安排这 $n$ 个产品的加工顺序，使得总加工时间最短（从第一个产品在 $A$ 车间开始加工到最后产品在 $B$ 产品完成加工）。

---

假设现在有编号为 $i$，$j$ 的两个产品，它们先后被加工。

假设先加工 $i$，那么加工这两个产品总用时为：$T_1=A_i+\max\{B_i,A_j\}+B_j.$

假设先加工 $j$，那么总用时为：$T_2=A_j+\max\{B_j,A_i\}+B_i.$

先加工 $i$ 总用时最短，当且仅当

$$A_i+\max\{B_i,A_j\}+B_j\lt A_j+\max\{B_j,A_i\}+B_i$$

让我们引入一个技巧：$\max\{A,B\}-A-B=\min\{A,B\}.$ 那么我们调整上式，即得：

$$\max\{B_i,A_j\}-B_i-A_j\lt \max\{B_j,A_i\}-B_j-A_i,\\ -\min\{B_i,A_j\}\lt-\min\{B_j,A_i\},\\ \min\{B_i,A_j\}\gt\min\{B_j,A_i\}.$$

分类讨论：

• 当 $A_i\le B_i$ 时，