贪心入门题单

这份题单根据文章《吃透贪心算法｜CSP-J/S 八大核心模型与真题策略全梳理》整理，目标是把常见贪心模型先刷成“看到题能归类、能说出选择规则”的程度。

做题时不要只记代码，建议每题都写清楚三件事：

1. 当前题的局部选择是什么？
2. 为什么这个局部选择不会影响全局最优？
3. 如果需要排序，排序规则能不能用交换相邻元素来解释？

一、性价比排序模型

核心思路：资源有限时，先选择单位收益更高或单位成本更低的对象。

• luogu P2240 【深基12.例1】部分背包问题题解
  • 模型：部分背包。
  • 贪心点：按单位重量价值从高到低排序，能完整拿就完整拿，剩余容量不足时分割物品。
• luogu P1208 [USACO1.3] 混合牛奶 Mixing Milk题解
  • 模型：低成本采购。
  • 贪心点：按牛奶单价升序购买，优先买便宜农户的牛奶。

二、时间调度模型

核心思路：时间类问题常见规则是“短任务优先”或“早结束优先”。

• luogu P1223 排队接水题解
  • 模型：排队等待时间最小。
  • 贪心点：接水时间短的人排在前面，减少后面所有人的等待贡献。
• luogu P1803 凌乱的yyy / 线段覆盖题解
  • 模型：最多不相交区间。
  • 贪心点：按结束时间升序排序，每次选择第一个不冲突的活动。

三、哈夫曼合并模型

核心思路：两两合并有代价时，每次优先合并当前最小的两个元素。

• luogu P1090 [NOIP 2004 提高组] 合并果子题解
  • 模型：哈夫曼合并。
  • 贪心点：小根堆维护果堆重量，每次取出最轻的两堆合并并累加代价。

四、单向线性遍历贪心

核心思路：从左到右扫描，只在当前位置做必要修正，不回头修改已经处理好的前缀。

• luogu P3817 小A的糖果题解
  • 模型：相邻限制修正。
  • 贪心点：若相邻两盒糖果总数超过限制，只减少右侧糖果，保证左侧前缀不再被破坏。
• luogu P5019 [NOIP 2018 提高组] 铺设道路题解
  • 模型：差分视角的线性贪心。
  • 贪心点：当前深度比前一个更深时，新增的深度差就是必须增加的操作次数。

五、双指针配对贪心

核心思路：排序后用左右指针，让最大值和最小值尝试配对，尽量利用限制空间。

• luogu P1094 [NOIP 2007 普及组] 纪念品分组题解
  • 模型：最少分组。
  • 贪心点：最贵物品若能和最便宜物品同组就配对，否则最贵物品单独成组。
• luogu P13256洛谷原题
  • 模型：每组最多两个元素的容量配对。
  • 贪心点：每次处理最大的文件；若它能和当前最小文件同盘就配对，否则最大的文件只能单独占一盘。
• luogu P4995 跳跳！题解
  • 模型：最大化相邻差值收益。
  • 贪心点：排序后交替选择高低两端，让每次跳跃高度差尽量大。

六、贪心顺序辅助搜索

核心思路：当局部选择不能直接保证全局最优时，仍可用贪心顺序优先处理约束最强的对象，减少搜索分支；最终正确性来自完整搜索。

• luogu P10483洛谷原题
  • 模型：降序搜索 + DFS 分支限界。
  • 贪心点：先安排更重的小猫，让容量约束尽早生效；但降序只优化搜索顺序，最优性由 DFS 枚举保证。

七、邻项交换排序模型

核心思路：当排序规则不直观时，比较相邻两个元素交换前后的优劣，推出自定义比较函数。

• luogu P1080 [NOIP 2012 提高组] 国王游戏题解
  • 模型：邻项交换排序 + 高精度。
  • 贪心点：按 左手数字 * 右手数字 从小到大排序，降低最大风险值。
• luogu P1012 [NOIP 1998 提高组] 拼数题解
  • 模型：字符串拼接排序。
  • 贪心点：若 a + b > b + a，则 a 应排在 b 前面。

八、单调栈贪心

核心思路：维护一个对答案最有利的单调结构，遇到更优元素时删除前面破坏最优性的元素。

• luogu P1106 删数问题题解
  • 模型：删数字得到最小数。
  • 贪心点：从左到右扫描，当前数字更小时，尽量删除前面更大的高位数字。

九、连续序列分组贪心

核心思路：有序序列中，能接到已有连续组时，优先接到当前长度最短的组，避免短组无法延长。

• luogu P4447 [AHOI2018初中组] 分组题解
  • 模型：连续分组。
  • 贪心点：新数值 x 优先接到末尾为 x - 1 且长度最短的分组；无法接入时新建组。

十、有限资源低成本选取模型

核心思路：资源总量有限时，优先完成消耗更低的任务，在资源耗尽前让完成数量最大。

• luogu P1478 陶陶摘苹果（升级版）题解
  • 模型：有限体力下最多选择。
  • 贪心点：先筛掉够不到的苹果，再按采摘体力升序选择，直到体力不足。

复盘要求

每做完一题，建议在笔记里补一段：

1
2
3
4模型：
排序 / 选择规则：
为什么局部最优能推出全局最优：
如果换一种排序，哪里会出错：

贪心题的训练重点不是背模板，而是能从题面限制中推出“当前最应该做什么”，并能解释这个选择不会让后续变差。