算法备忘录·贪心

一直以来，没能系统学习算法，是我心中的痛；现在学了 y 总的算法基础课，做做笔记，希望能够有所收获。
这是第七节，贪心。

贪心

• 贪心：每次找局部最优解，就可以找到全局最优解。所以贪心一般要求函数是单峰的。
• 做法：猜 + 证明

区间

区间选点

• 问题：给定 $N$ 个闭区间 $\left[a_{i}, b_{i}\right]$, 请在数轴上选择尽量少的点, 使得每个区间内至少包含一个选出的点。
• 思路：
  1. 将每个区间按右端点从小到大进行排序
  2. 从前往后依次枚举每个区间
  • 如果当前区间中已包含点，则直接 pass
  • 否则，选择当前区间的右端点
• 证明：
  1. 设 $ans$ 是最优解，$cnt$ 是上述得到的可行解。显然有 $ans \leq cnt$
  2. 由于上述思路最后得到的是 $cnt$ 个两两不相交的区间，覆盖每个区间至少需要 $cnt$ 个点，因此 $ans \geq cnt$
  3. 故 $ans = cnt$

最大不相交区间数量

• 问题：给定 $N$ 个闭区间 $[a_i,b_i]$，请在数轴上选择若干区间，使得选中的区间之间互不相交。
• 思路：完全相同于区间选点
• 证明：
  1. 设 $ans$ 是最优解，$cnt$ 是上述得到的可行解。显然有 $ans \geq cnt$
  2. 假设 $ans \geq cnt$，那么根据最优解的定义，最多有 $ans$ 个不相交的区间，因此至少需要 $ans$ 个点才能覆盖所有区间。而该思路只需 $cnt$ 个点就能覆盖全部区间，矛盾。因此 $ans \leq cnt$
  3. 故 $ans = cnt$

区间分组

• 问题：给定 $N$ 个闭区间 $\left[a_{i}, b_{i}\right]$, 请将这些区间分成若干组, 使得每组内部的区间两两之间（包括端点）没有交集, 并使得组数尽可能小。
• 思路：
  1. 将每个区间按左端点从小到大进行排序
  2. 从前往后依次枚举每个区间，判断能否将其放到某个现有组中，即 l[i]>max_r
  • 如果不存在这样的组，开一个新的组并放入
  • 如果存在这样的组，放入，并更新当前组的 max_r
• 证明：
  1. 设 $ans$ 是最优解，$cnt$ 是上述得到的可行解。显然有 $ans \leq cnt$
  2. 考虑开辟第 $cnt$ 个组的时刻：此时已经开辟了 $cnt-1$ 个组。对于第 $i$ 个区间，由于不能放入现有组中，所以有 $max_r \geq L_i$。又因为区间是按 $L$ 从小到大排列的，所以 $L_i$ 一定会与前 $cnt-1$ 组有区间均相交，所以必须要开辟新的组，即至少需要 $cnt$ 组。这因此 $ans \geq cnt$
  3. 故 $ans = cnt$

区间覆盖

• 问题：给定 $N$ 个闭区间 $\left[a_{i}, b_{i}\right]$ 以及一个线段区间 $[s, t]$, 请你选择尽量少的区间, 将指定线 段区间完全覆盖。输出最少区间数, 如果无法完全覆盖则输出 -1。
• 思路：
  1. 将每个区间按左端点从小到大进行排序
  2. 从前往后依次枚举每个区间，在所有能覆盖目标左端点的区间中，选择右端点最大的区间。然后重新将目标左端点更新成右端点的最大值
• 证明：
  1. 假设最优解的方案和可行解的方案不同，那么可以证明最优解中较短的区间可以被可行解区间中对应的区间替换。（调整法证明）
  2. 故 $ans = cnt$

Huffman 树

合并果子

• 问题：即 Huffman 树问题
• 思路：每次选最小的两个数合并
• 证明：
  • 命题 1：最小的两个点深度一定最深，且可以互为兄弟（说明什么是局部最优）
  • 命题 2：最优树用一个非叶结点代替这两个结点后，依旧是最优树（说明为什么局部最优能够实现全局最优）

排序不等式

排队打水

• 问题：有 $n$ 个人排队到 $1$ 个水龙头处打水，第 $i$ 个人装满水桶所需的时间是 $t_i$，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？
• 思路：当 $t_1,t_2,\cdots,t_n$ 按升序排列时，所有人的等待时间最少
• 证明：
  • 等待时间总和：$0+\left(t_{1}\right)+\left(t_{1}+t_{2}\right)+\left(t_{1}+t_{2}+t_{3}\right)+\cdots+\left(t_{1}+t_{2}+\cdots+t_{n}-1\right)=t_{1}(n-1)+t_{2}(n-2)+\cdots+t_{n-1}$
  • 反证：如果交换其中 $i$ 和 $j$，那么总和时间一定会变长

绝对值不等式

货仓选址

• 问题：数轴上有 $n$ 个点，在数轴上找一个点，使得那 $n$ 个点到这个点的距离之和最小
• 思路：假设升序排序后的 $n$ 个数为 $x_{1}, x_{2}, \cdots, x_{n}$，则总距离可表示为 $\begin{aligned} f(x) &=\left|x_{1}-x\right|+\left|x_{2}-x\right|+\cdots+\left|x_{n}-x\right| \\ &=\left(\left|x_{1}-x\right|+\left|x_{n}-x\right|\right)+\left(\left|x_{2}-x\right|+\left|x_{n-1}-x\right|\right)+\cdots \\ & \geqslant\left(x_{n}-x_{1}\right)+\left(x_{n-1}-x_{2}\right)+\cdots \end{aligned}$
  • 取 a[n / 2] 即可取得等号
• 证明：绝对值不等式

推公式

耍杂技的牛

• T：125. 耍杂技的牛
• 思路：按照 $w_i + s_i$ 的从小到大排最优
• 证明：交换任意两项证明它的危险系数会增加

---

算法备忘录系列目录：
第一节 算法备忘录·基础算法
第二节 算法备忘录·数据结构
第三节 算法备忘录·杂项
第四节 算法备忘录·搜索与图论
第五节 算法备忘录·数学知识
第六节 算法备忘录·动态规划
第七节 算法备忘录·贪心
第八节 算法备忘录·时空复杂度分析
第九节 算法备忘录·杂项