- C++
【算法1-5】贪心 按难度星级评级(从小到大排序)
- 2025-5-26 22:49:51 @
https://www.luogu.com.cn/training/110#information
按难度星级评级(从小到大排序)
一星(基础入门)
- P2240 【深基12.例1】部分背包问题
- P1223 排队接水
- P1803 凌乱的yyy / 线段覆盖
- P3817 小A的糖果
- P1478 陶陶摘苹果(升级版)
- P1208 [USACO1.3] 混合牛奶 Mixing Milk
- P1094 [NOIP 2007 普及组] 纪念品分组
- P4995 跳跳!
二星(基础进阶)
- P1090 [NOIP 2004 提高组] 合并果子
- P1106 删数问题
- P5019 [NOIP 2018 提高组] 铺设道路
三星(中等难度)
- P4447 [AHOI2018初中组] 分组
四星(较高难度)
- P1080 [NOIP 2012 提高组] 国王游戏
按知识点分类
经典贪心模型
- 贪心选择性质:
- 部分背包问题:P2240(按单位价值贪心)
- 排队接水:P1223(按接水时间从小到大排序)
- 混合牛奶:P1208(按价格贪心选择)
- 区间贪心:
- 线段覆盖:P1803(区间选点/区间覆盖问题)
贪心策略应用
- 哈夫曼思想:P1090 合并果子(每次选最小的两个合并)
- 序列操作贪心:
- 删数问题:P1106(每次删除高位最大数字)
- 纪念品分组:P1094(双指针贪心配对)
- 跳跃问题:P4995 跳跳!(相邻跳跃距离贪心选择)
二维贪心与状态分析
- 二维排序贪心:
- 国王游戏:P1080(按左右手乘积排序,需数学证明贪心策略)
- 分组问题:P4447 [AHOI2018初中组] 分组(按区间右端点排序分组)
- 区间覆盖变形:P5019 铺设道路(差分思想+贪心计算层数)
贪心与模拟
- 摘苹果问题:P1478 陶陶摘苹果(升级版)(条件判断贪心选择)
- 糖果分配:P3817 小A的糖果(简单条件贪心)
1 条评论
-
admin SU @ 2025-5-26 22:50:01
按难度星级评级(从小到大排序)
一星(基础入门)
- P2240 【深基12.例1】部分背包问题:简单的贪心策略应用,按单位价值贪心选取物品。
- P1223 排队接水:按接水时间从小到大排序的经典贪心,思路较直接。
- P1803 凌乱的yyy / 线段覆盖:区间贪心的基础应用,按区间右端点排序贪心选择。
- P3817 小A的糖果:简单条件下的贪心选择问题。
- P1478 陶陶摘苹果(升级版):在一定条件下进行贪心选择,逻辑不复杂。
- P1208 [USACO1.3] 混合牛奶 Mixing Milk:按价格进行贪心选择,是基础的贪心模型。
- P1094 [NOIP 2007 普及组] 纪念品分组:利用双指针进行贪心配对,属于基础应用。
- P4995 跳跳!:在相邻跳跃距离上进行贪心选择,规则较明确。
二星(基础进阶)
- P1090 [NOIP 2004 提高组] 合并果子:类似哈夫曼树构建的贪心,需要理解每次合并最小元素的策略。
- P1106 删数问题:在数字序列上进行贪心删除,需要理解高位优先删除大数字的逻辑。
- P5019 [NOIP 2018 提高组] 铺设道路:结合差分思想的贪心应用,有一定思维难度。
三星(中等难度)
- P4447 [AHOI2018初中组] 分组:按区间右端点排序进行分组的贪心问题,需要处理好分组逻辑。
四星(较高难度)
- P1080 [NOIP 2012 提高组] 国王游戏:涉及二维排序的贪心,还需数学证明贪心策略的正确性,难度较大。
按知识点分类
经典贪心模型
- 背包类:P2240 【深基12.例1】部分背包问题(按单位价值贪心)。
- 排队问题:P1223 排队接水(按接水时间排序贪心) 。
- 区间问题:P1803 凌乱的yyy / 线段覆盖(区间选点贪心)。
- 资源分配:P1208 [USACO1.3] 混合牛奶 Mixing Milk(按价格贪心选择资源)。
序列贪心
- 数字序列:P1106 删数问题(在数字串上按高位到低位贪心删除)。
- 物品序列:P1094 [NOIP 2007 普及组] 纪念品分组(对物品序列双指针贪心配对)。
构造类贪心
- 类似哈夫曼树:P1090 [NOIP 2004 提高组] 合并果子(每次合并最小元素构造最优解)。
综合应用
- 游戏模拟类:P3817 小A的糖果、P4995 跳跳!(在特定游戏规则下进行贪心决策)。
- 差分与贪心:P5019 [NOIP 2018 提高组] 铺设道路(利用差分思想辅助贪心求解)。
- 二维贪心:P1080 [NOIP 2012 提高组] 国王游戏(二维排序并证明贪心策略)。
- 分组贪心:P4447 [AHOI2018初中组] 分组(按区间右端点进行分组贪心)。
- 1