来自 曙光 21 天打卡挑战 - Day3
继续学习贪心算法
证明贪心算法可以有如下步骤：
- 证明贪心选择性质，即选择局部问题的最优解可以构建全局最优解（此处的“可以构建”指的是，一定存在一个最优解，使得局部最优解是这个最优解的一部分）
常用证明法：替换法。假设存在一个最优解，证明根据贪心策略选择的第一步可以替换掉该最优解的第一步，而不会使解变差。
- 证明最优子结构，即一个问题的最优解包含其子问题的最优解。用于保证对这个小一点的子问题再次应用贪心策略，可以导向最优解。
其他方法：交换论证、数学归纳法。
说实话，目前对贪心算法的证明理解没有到能用严格数学语言描述的程度。打算明天继续深入严格证明和特殊题目（临项交换、后悔法），希望能构建缜密的逻辑。
杂项
几个 Linux 小知识：
- curl 指令。它可以向一个 url 发送 http 请求。常见的参数是 -fsSL
- tee 指令：将标准输入流同时导向一个文件和标准输出流
- /dev/null: 黑洞文件，一般用于丢弃输出
C 艹 小知识：
std::sort对std::pair类型的数组排序时，先对 first 升序，first 相同时再对 second 升序