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

2026-09-05 来自 上海
0


























有帮助,赞一个