吃透贪心算法｜CSP-J/S 八大核心模型与真题策略全梳理
在 CSP-J、CSP-S 竞赛中，贪心是性价比极高的考点：代码短、思考门槛低于动态规划，且每年普及组、提高组都会稳定出 1~2 道大题。很多同学能看懂贪心答案，却无法自主推导最优选择规则，核心问题是没有归纳固定的贪心模型。本文结合洛谷 14 道经典竞赛真题，分类拆解 CSP 高频贪心模型、通用解题策略，覆盖普及组到提高组全部常考题型。
目录
1. 性价比排序模型
2. 时间调度模型
3. 哈夫曼合并模型
4. 单向线性遍历贪心
5. 双指针配对贪心
6. 邻项交换排序模型
7. 单调栈贪心模型
8. 连续序列分组贪心
9. 竞赛贪心总结与解题思路
一、性价比排序模型（物品最优选取）
核心逻辑：把物品按照单位收益 / 单位成本排序，优先选择性价比最高的物品，适用于资源有限、物品可分割或按需选取的场景。
P2240 部分背包问题贪心策略：计算每件物品单位重量价值，从高到低排序。优先完整取性价比最高物品，背包剩余容量不足时分割物品填充，最大化总价值。
P1208 混合牛奶贪心策略：按农户牛奶单价升序排序，优先采购低价农户全部牛奶，依次向后采购，用最少成本凑齐目标牛奶总量。
二、时间调度模型（区间、排队时间最优）
核心逻辑：处理时间、区间类问题，遵循「早结束优先、短任务优先」原则，减少全局时间损耗，是普及组必考模型。
P1223 排队接水贪心策略：所有人按接水时间从小到大排序，用时短的人先接水，最小化所有人的总等待时长。
P1803 凌乱的 yyy（线段覆盖）贪心策略：所有活动按结束时间升序排序，每次选择结束最早、且不与已选活动冲突的赛事，选出最多不重叠活动。
三、哈夫曼合并模型（两两合并最小代价）
核心逻辑：借助小根堆，每次取出当前数值最小的两个元素合并，重复操作直到只剩一个元素，小数优先合并可减少重复累加开销。
代表真题：P1090 合并果子 贪心策略：用小根堆维护果堆重量，每次取出两堆最轻果子合并，累加合并消耗，最终得到全局最小总消耗，是标准哈夫曼树贪心模板。
四、单向线性遍历贪心（区间填充、相邻限制）
核心逻辑：从左至右单向扫描数组，仅对当前位置做局部修正，利用前一位操作的剩余效果减少操作次数，无需回溯。
P3817 小 A 的糖果贪心策略：从左向右遍历相邻两盒糖果，若两盒总数超过限制，仅减少右侧糖果，一次操作同时约束两组相邻数据，最小化吃掉糖果总数。
P5019 铺设道路贪心策略：顺序遍历坑的深度，若当前坑比前一个更深，累加深度差值；浅层坑可被前一次填充顺带填平，差值即为新增操作次数，统计最少铺路次数。
五、双指针配对贪心（首尾匹配最大化利用）
核心逻辑：序列排序后用左右双指针，最大、最小元素配对，充分利用空间 / 差值限制，分为「最小分组」和「最大收益」两类考法。
P1094 纪念品分组贪心策略：纪念品升序排序，左指针取最便宜、右指针取最贵；两者总价不超过上限则分为一组，否则贵重物品单独一组，最小化分组数量。
P4995 跳跳！贪心策略：石头高度升序排序，左右指针交替跳跃（最高→最低→次高→次低），每次选取剩余高度差最大的两块石头，最大化跳跃总体力。
六、邻项交换排序模型（自定义比较规则）
核心逻辑：无法直观排序时，通过交换相邻两个元素证明最优顺序，自定义排序比较函数，提高组高频考点。
P1080 国王游戏贪心策略：证明得出大臣排序规则：左手数字 × 右手数字更小的人排在前面，排序后计算每位大臣金币，取全局最大值，需搭配高精度运算。
P1012 拼数贪心策略：数字转为字符串，自定义比较规则
a+b > b+a；若 a 拼接 b 数值更大，则 a 前置，按规则降序拼接得到最大整数。
七、单调栈贪心（删数字维护最优序列）
核心逻辑：借助栈单调递增 / 递减特性，删除破坏最优性的高位数字，保留字典序最小 / 最大结果。
代表真题：P1106 删数问题贪心策略：从左到右扫描数字，栈顶数字大于当前数字且仍有删除次数时，弹出栈顶大数；遍历结束仍有删除名额，删除末尾数字，得到最小整数。
八、连续序列分组贪心（提高组中档题）
核心逻辑：有序序列中，连续数字优先拼接成组，新元素优先接入长度最短的连续分组，避免单一分组耗尽连续数值。
代表真题：P4447 [AHOI2018 初中组] 分组贪心策略：所有人实力升序排序，新数值 x 优先接入末尾为 x-1、长度最短的分组；无匹配分组则新建组别，答案取所有分组的最小长度。
九、有限资源低成本选取模型
核心逻辑：资源总量存在上限时，优先完成消耗代价更低的任务，在资源耗尽前完成最多任务。
代表真题：P1478 陶陶摘苹果（升级版）贪心策略：筛选伸手可触及的苹果，按采摘消耗体力升序排序，优先摘省力苹果，直到体力耗尽，获取最多苹果数量。
竞赛贪心学习总结
普及组核心掌握：性价比、区间调度、哈夫曼、单调栈、双指针配对 5 类模型，覆盖初赛、入门大题；
提高组重点突破：邻项交换排序、连续序列分组两类难题，常作为 CSP-S 第二题出现；
贪心通用解题思路：
① 观察题目是否存在局部最优能推出全局最优；
② 归纳排序 / 选取规则，尝试交换相邻元素验证正确性；
③ 匹配对应模型，套用固定代码模板快速实现。
贪心没有万能模板，但所有 CSP 真题都能归入以上 8 大类模型。刷题时不要只记代码，重点理解「为什么这个选择是最优的」，考场遇到新题型才能自主推导贪心策略。
贪心算法的解题策略灵活多变，没有固定的解题套路。做题时需要我们仔细剖析题目条件，结合题意梳理核心逻辑，归纳并匹配对应的贪心策略，同时务必验证策略的正确性，确认局部最优解能够推导全局最优解后，再编写代码实现。本文是本人结合CSP-J/S历年真题自主整理的贪心核心模型笔记，内容难免存在不全、遗漏或不足之处，欢迎各位同学、老师批评指正、多多交流。
