贪心信号
关键词：“最多”,“最少”,“最大”,“最小”
特征：排序后有单调性，每步选择只看当前状态，个元素之间独立或仅有简单约束。
验证：交换论证（找反例）
典型场景：按某个属性排序后依次选取；每次选当前最优且不影响后续最优性。
时间复杂度：O(nlogn)(开销主要在排序），N ≤\le≤ 1e6
DP信号
关键词：”恰好“，”方案数“，”最大价值“。
特征：有约束导致选择冲突、一个选择会影响另一个选择的可行性。
验证：先假设贪心，看看能否构造出”贪心选了A导致错过更好的B的情况“。
典型问题：背包问题、序列选择、区间问题。
时间复杂度：O(n2n^2n2)以上 (N ≤\le≤ 1e4)。
二分信号
关键词：”最大值最小“，”最小值最大“
套路：二分模板+check函数。
典型场景：”最短距离最大化“，”最大段和最小化“。
时间复杂度：O(nlogn)（n开销在Check函数，logn开销在二分）(N ≤\le≤ 1e6)
技巧：看到最值问题，先猜贪心交换论证（找反例）出错，考虑DP、二分
1.举反例
先思考自己要证明的是什么。
然后寻找能否构造出相反结论的样例。
2.交换论证法
题意：n个人排队接水，第i个人的接水时间是tit_iti 。求排列顺序使得平均等待时间最少。
第一步：猜策略。 猜”按接水时间从小到大排序“。
第二步：假设最优解中存在逆序。 假设在某个最优的排列中，有两个相邻的人A和B，A排在B前面，但tAt_AtA >tBt_BtB （即接水慢的A排在了快的B前面，违反了策略）
第三步：交换A和B，算变化。 设A前面有k个人，我们只看A、B以及他们后面的人的等待时间的变化。
交换前：
* A的等待时间：前面k个人的接水时间之和（设为W）
* B等待的时间：W+tAt_AtA
* A和B对后面人的等待贡献：每个后面的人都要等tAt_AtA +tBt_BtB
交换后：
* B的等待时间：W
* A的等待时间：W+tBt_BtB
* A和B对后面的人的等待贡献：还是tAt_AtA +tBt_BtB
