• 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 条评论

  • @ 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