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

全部评论 1
- 置顶
此帖针对CSP-J组复赛前三题,希望对你有帮助

2026-09-06 来自 上海
1





















有帮助,赞一个