贪心
关键词：“最大，最小”等最值问题。
验证：交换论证。
时间复杂度：O（n）或者O(nlogn)，适用于N<1e6
*交换论证法讲解:*在最优解中随便挑两个相邻元素交换一下，如果结果不会变得更好，说明排序方式正确的。
第一步：定策略。定出你的贪心策略，比如“按结束时间排序”，“按重量排序”等等。
第二部：假设存在一种情况与排序方式不同。假设A在B的前面，且t[A] > t[B].把A和B的位置互换，得到一个新方案S'，用具体的数学式子算出S和S'的结果差距：
. 如果S'不比S差，说明交换更好 => 贪心策略正确；
. 否则，说明贪心策略错误，需更换策略。
举例：在排队接水问题中,交换前时间：前k个人是W,W……W,T[a],后面每个人都要等T[a] + T[b];
交换后时间：前k个人是W,W……W + T[a]，后面每个人也要等T[a] + T[b].
——————————————————————————————————————————————————————————
二分
二分的实质：枚举。写二分的时候要先考虑好枚举对象和范围。
二分答案：用来特定解决"最大值最小"，“最小值最大”的问题。
| 1.定二分对象：“锯片高度”，“最大段和”，“最短跳跃距离”.
| 2.确定什么时候改变区间。
| 3.写check函数，用一次贪心/扫描判断/最短路/其他算法，判断能不能做到。
——————————————————————————————————————————————————————————
反悔贪心(S组新增重点)
普通贪心:每一步的选择一旦做出就永远不亏。
反悔贪心：带“容量/名额/时间”等限制的最优选取 ———— 你在早期做出的选择，到后期可能被证明“当初不该选它”。
反悔贪心和DP的区别：反悔贪心的前提是每个物品占用的“名额”必须是等价的，如果物品占用“名额/空间”不是等价的，就必须使用DP。
| 1.按物品的某个维度顺序（长按截止时间/到达顺序）。
| 2、维护一个小根堆，堆里存“已经选进方案的收益值”。
| 3.一次考虑每个物品：
————a.若当前还有空位，继续选，收益入堆。
————b.如果没有空位，考虑当前物品收益 》 堆顶（已选中最小收益的那个），反悔：弹出堆顶，把当前物品进堆。
| 4.堆中所有元素之和 = 答案.
