最值问题(1)9.5

钟语嫣

2026-09-12 19:00:23

发布于：上海

11阅读

0回复

0点赞

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

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

二分信号：
关键词："最大值最小"、"最小值最大"。
套路：二分模板+check函数。
典型场景："最短距离最大化"、"最大段和最小化"。
时间复杂度： $O(n log n)$ (n开销在check函数，log n 开销在二分) (N $\le$ 1e6)。

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

1、举反例：
先思考自己要证明的是什么。
然后寻找能否构造相反结论的样例。
2、交换认证法：
例:
题意:n个人排队接水，第i个人的接水时间是 $t_i$ 。求排列顺序使得平均等待时间最少。
第一步：猜策略。猜"按接水时间从小到大排序"。
第二步：假设最优解中存在逆序。假设在某个最优的排列中，有两个相邻的人A和B，A排在B前面，但 $t_a$ $>$ $t_b$ (即接水慢的A排在了快的B前面，违反了策略)
第三步：交换A和B，算变化。设A前面有k个人，我们只看A和B以及他们后面的人的等待时间的变化。