最值问题

宇宙超级无敌霸王龙

2026-09-05 19:24:33

发布于：上海

6阅读

0回复

0点赞

贪心信号：
关键词：最大，最小，最多，最少。
特征：排序后有单调性、每步选择只看当前状态、各元素之间独立或仅有简单约束。
验证：交换论证（找反例）
经典场景：按某个属性排序后依次选取；每次选当前的最优且不影响后续最优性。
时间复杂度： $O(nlogn)$ （主要开销在排序），N <= 1e6

DP信号：
关键词：恰好，方案数，最大价值。
特征：有约束导致选择的冲突、一个选择会影响另一个选择的可行性。
验证：先假设贪心，看看能否构造出“贪心选了A导致错过了更好的B的情况”。
经典场景：背包问题、序列选择、区间问题。
时间复杂度： $O(n^2)$ 以上（N<=1e4)

二分信号：
关键词：”最大值最小“，”最小值最大“。
套路：二分模板+check函数。
经典场景”最短距离最大化“，”最大段最小化“。
时间复杂度： $O(nlogn)$ （n开销在check函数，logn开销在二分）(N<=1e6)

技巧：看到最值问题，先猜贪心，如果贪心交换论证（找反例）出错，考虑DP、二分。

1、举反例：
先思考自己要证明的是什么。
然后寻找能否构造出相反结论的样例

2、交换论证法
题意：n个人排队接水，第i个人的接水时间是 $t_i$ 。求排列顺序使得平均等待时间最少。
第一步：猜策略。猜”按接水时间从小到大排序“
第二步：假设最优解中序在逆序。假设在某个最优的排序中，有两个相邻的人A和B，A排在B前面。但 $t_A$ > $t_B$ （即接水慢的A排在了快的B前面，违反了策略）
第三步：交换A和B，算变化。设A前面有k 个人，我们只看A、B以及他们后面的人的等待时间变化。