最值问题
1.识别信号
贪心信号
关键词:"最多","最少","最大","最小"。
特征:排序后有单调性,每步选择只需要考虑当下的最优解即可。
验证:交换论证能证明贪心的正确性。
> 典型场景:按某个属性排序后便利。依次选取物品,每次只考虑当下的最优解且不影响后续的最优性。
时间复杂度:O(nlogn),N<=1e6O(nlogn), N <= 1e6O(nlogn),N<=1e6 时间开销主要在排序。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
DP信号
关键词:"最大 or 最小","恰好","方案数"。
特征:有约束导致选择冲突,贪心策略会找到反例,一个选择会影响另一个选择的可行性
验证:举反例——尝试贪心看看能不能构造出"贪心选了A导致错过了更好的B的情况"。
> 典型场景:序列选择(前面的数字选或不选会影响后面)、背包(容量有限,每个物品要考虑拿或不拿,每个决策都会影响后续的选择),区间问题(只能操作相邻的区间元素)。
时间复杂度:一般大于 O(n2),N<=1e4O(n^2), N <= 1e4O(n2),N<=1e4。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二分信号
关键词:"最大值最小","最小值最大"。
套路:二分答案 + check函数。
> 典型场景:"最短距离最大化","最大段和最小化"。
时间复杂度:O(nlogn),N<=1e6O(nlogn), N <= 1e6O(nlogn),N<=1e6。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
总结
看到最值问题 -> 先猜贪心 -> 交换论证验一下 -> 验证通过选贪心 -> 否则转DP,二分。
2.交换论证法
* 按照时间排序。先随便写两个总时间,考虑交换后有没有可能更有。
* 按照开始时间排序
* 按照结束时间排序