啥都没有
2026-09-06 11:57:47
发布于:上海
贪心
关键词:“最大”“最小”等最值问题
验证:交换论证
时间复杂度:O(n)或O(nlogn) 适用于n <= 1e6
交换论证法讲解:在最优解中随便挑两个相邻元素交换一下,如果结果不会变的更好,说明我的排序方式就是对的
第一步:定策略。定出你的贪心策略,比如:“按结束时间排序”“按重量排序”等等。
第二步:假设存在一种情况与排序方式不同。假设a在b的前面,且ta > tb。把a和b的位置互换,得到一个新方案s',用具体的数学式算出s'和s的结果差距
如果s'的结果不比s差,说明交换不亏/更好 ,说明贪心结果正确
否则,说明贪心策略是错误的,需要更换策略
举例:
交换前时间:前k个人是w,w,w+ta,后面的人ta+tb
交换后时间:前k个人是w,w,w+tb,后面的人ta+tb
二分
二分的实质:枚举。写二分的时候要先考虑好枚举的对象和枚举的范围
二分答案:用来特定的解决“最大值最小”“最小值最大”的问题
1.定二分对象:“锯片高度”“最大段和”“最短跳跃距离”
2.确定什么时候改变区间
3.写check函数,用一次贪心/扫描判断/最短路/其他算法,判断能不能做到
反悔贪心
普通贪心:每一步的选择一旦做出就永远不亏
反悔贪心:带“容量/名额/时间”等限制的最优选举 --- 你在早期做的选择,到后期可能被证明“当初不该选他”
例如:每天能许一个愿望,每个愿望都有对应的价值
反悔贪心和dp的区别:反悔贪心的前提是每个物品占用的“名额”必须是等价的,如果物品占用的“名额/空间”不是等价的,就必须用dp。
1.按物品的某个维度排序(常按截止时间/到达顺序)
2.维护一个小根堆,堆里存“已经选进方案的收益值”
3.依次考虑每个物品:
a:如果当前还有空位,就继续选,收益入堆
b:如果没有空位,考虑当前物品收益>堆顶(已选中收益最小的那个),反悔:弹出堆顶,把当前物品进堆
4.堆中所有元素之和 = 答案
这里空空如也
















有帮助,赞一个