一、核心原理什么是贪心1.1 定义贪心把整体问题分解成多个步骤在每个步骤都选取当前步骤的最优方案直至所有步骤结束。核心性质每次采用局部最优最终结果就全局最优。1.2 贪心 vs 动态规划对比项贪心动态规划决策方式当前最优不回退考虑所有可能保存最优时间复杂度通常 O(n) 或 O(n log n)通常 O(n²) 或更高适用条件具有贪心选择性质具有最优子结构正确性证明需要证明局部最优全局最优递推公式保证1.3 如何判断能否用贪心两个关键性质最优子结构性质问题的最优解包含子问题的最优解贪心选择性质可以通过局部最优的选择得到全局最优实用技巧举反例如果能找到一个反例说明贪心不对就不能用。二、经典反例硬币问题2.1 能用贪心的情况硬币1元、2元、5元数量不限支付M元要求硬币数最少。贪心策略每次选最大面值。支付9元522 3个硬币 ✓2.2 不能用贪心的情况硬币1元、2元、4元、5元、6元支付9元。贪心策略621 3个硬币最优解45 2个硬币 ✗结论不是所有局部最优都能得到全局最优三、贪心经典题型题型核心思想蓝桥杯例题排序双指针排序后两头凑P532 分箱问题堆/优先队列每次取最小/最大P545 石子合并从左往右扫遇到不同就处理P209 翻硬币排序后对应一大一小配对数组乘积问题四、例题 1石子合并蓝桥杯 P545项目内容链接https://www.lanqiao.cn/problems/545/learning/类型贪心 堆优先队列核心每次选最小的两个合并题目描述n个部落人数分别为t[i]。每次合并两个部落花费为两部落人数之和。求合并成一个部落的最小总花费。贪心证明关键观察人数少的部落越早合并被计算的次数越多因为它会成为更大部落的一部分继续参与合并。策略每次选人数最少的两个部落合并这样小数被多次计算的总代价最小。证明假设当前最小两个为a b如果先合并其他两个c d则后续a还要再合并总代价会增加。完整代码importheapq nint(input())alist(map(int,input().split()))# 转换成小根堆heapq.heapify(a)ans0whilelen(a)2:# 取出两个最小的xheapq.heappop(a)yheapq.heappop(a)# 合并costxy anscost# 新部落入堆heapq.heappush(a,cost)print(ans)推演过程n4, t[1, 2, 3, 4] 初始堆: [1, 2, 3, 4] 第1轮: 取1,2, 合并3, ans3, 堆[3, 3, 4] 第2轮: 取3,3, 合并6, ans9, 堆[4, 6] 第3轮: 取4,6, 合并10, ans19, 堆[10] 输出: 19 验证其他策略: 如果先合并3,47, 堆[1,2,7] 再合并1,23, ans10, 堆[3,7] 再合并3,710, ans20, 堆[10] 总花费20 19贪心更优 ✓复杂度分析指标复杂度说明时间O(n log n)堆操作O(log n)共n-1次空间O(n)堆的空间关键细节坑点说明必须用堆每次找最小用堆O(log n)排序O(n log n)但删除麻烦heapq是小根堆Python 默认小根堆大根堆存负数合并后入堆新部落继续参与后续合并五、例题 2分箱问题蓝桥杯 P532项目内容链接https://www.lanqiao.cn/problems/532/learning/类型贪心 排序 双指针核心大的和小的凑一起不浪费空间题目描述纪念品价格上限wn个纪念品每组最多两件价格之和 w。求最少分组数。贪心证明策略排序后最便宜的和最贵的凑一组。能凑就凑不能凑贵的单独一组。证明设最便宜的为a最贵的为b。如果a b w则a可以和任何人配对因为其他人都 b。让a和b配对不浪费a的配对能力。如果a b w则b无法和任何人配对因为a是最便宜的b必须单独一组。完整代码wint(input())nint(input())a[int(input())for_inrange(n)]a.sort()l,r0,n-1ans0whileTrue:iflr:# 剩一个单独装ans1breakiflr:# 装完了breakifa[l]a[r]w:ans1l1r-1else:ans1r-1print(ans)推演过程w10, n4, a[1, 2, 8, 9] 排序: [1, 2, 8, 9] l0(1), r3(9): 191010 → 配对, ans1, l1,r2 l1(2), r2(8): 281010 → 配对, ans2, l2,r1 l2r1 → 结束 输出: 2与石子合并的对比对比项石子合并 P545分箱问题 P532贪心策略每次选最小的两个最小配最大数据结构堆动态维护排序双指针核心思想小数尽早合并减少重复计算充分利用空间不浪费配对机会时间复杂度O(n log n)O(n log n)六、例题 3翻硬币蓝桥杯 P209项目内容链接https://www.lanqiao.cn/problems/209/learning/类型贪心 从左往右扫描核心遇到不同就翻一个位置最多翻一次题目描述初始状态s目标状态t每次只能同时翻转相邻两个硬币。求最少操作次数。贪心证明关键观察从左往右第一个不同的位置必须翻不翻就永远不同翻这个位置时只能连带翻右边相邻的一个位置最多翻一次翻两次等于没翻策略从左往右扫描遇到s[i] ! t[i]就翻i和i1。完整代码slist(input())tlist(input())nlen(s)ans0foriinrange(n-1):# 最后一个不能作为翻转起点ifs[i]t[i]:continue# 必须翻 i 和 i1s[i]t[i]# 翻后等于目标# 翻转 i1s[i1]*ifs[i1]oelseoans1# 检查最后一个是否匹配ifs[-1]t[-1]:print(ans)else:print(-1)# 无法完成推演过程s **oo***oooo t oooo***oooo i0: s[0]*, t[0]o, 不同翻0和1 s[0]*→o, s[1]*→o s oooo***oooo t ✓ ans 1 输出: 1关键细节坑点说明只能翻相邻两个翻i必须连带翻i1一个位置最多翻一次翻两次等于没翻所以贪心正确最后要检查最后一个位置可能无法匹配无法完成输出-1如果最后不匹配说明无解七、例题 4数组乘积最小贪心排序项目内容来源蓝桥云课贪心专题类型贪心 排序核心大配小小配大题目描述两个长度为n的正整数数组a和b可以任意排序。求Σ a[i] * b[i]的最小值。贪心证明策略a从小到大排序b从大到小排序然后对应位置相乘。证明以 n2 为例设a1 a2,b1 b2策略1大配小a1*b2 a2*b1策略2大配大a1*b1 a2*b2差值(a1*b2 a2*b1) - (a1*b1 a2*b2) a1*(b2-b1) a2*(b1-b2) (a1-a2)*(b2-b1)因为a1 a2所以a1-a2 0b2 b1所以b2-b1 0乘积 0。所以策略1 策略2大配小更优。完整代码nint(input())alist(map(int,input().split()))blist(map(int,input().split()))a.sort()# a 从小到大b.sort(reverseTrue)# b 从大到小ans0foriinrange(n):ansa[i]*b[i]print(ans)推演过程n3, a[1, 2, 3], b[4, 5, 6] a排序: [1, 2, 3] b排序: [6, 5, 4] 乘积: 1*6 2*5 3*4 6 10 12 28 验证其他配对: a[1,2,3], b[4,5,6] (同序): 1*4 2*5 3*6 41018 32 28 ✓ a[1,2,3], b[5,4,6]: 1*5 2*4 3*6 5818 31 28 ✓八、贪心算法总结8.1 常见贪心策略策略适用场景例题排序双指针配对、分组P532 分箱堆/优先队列动态取最值P545 石子合并从左往右扫翻转、覆盖P209 翻硬币大配小/小配大乘积、差值最小数组乘积按结束时间排序区间调度活动安排8.2 贪心正确性验证方法直觉验证策略看起来合理小规模枚举n2,3 时验证所有情况反例寻找尝试构造让贪心失败的例子交换论证假设最优解和贪心解不同通过交换证明贪心不差于最优九、学习心得贪心的本质是短视的智慧。每一步只看当前最优但前提是局部最优全局最优。三句话记住贪心先排序80%的贪心题需要先排序举反例不确定时构造小数据验证证明难实用易竞赛中先写贪心如果WA再换DP贪心 vs 动态规划的决策流程看到最优问题 → 想贪心 → 举反例验证 → 反例成立→ 是用DP否用贪心
