1. 贪心算法在蓝桥杯Java备赛中的分量第6天的备战我把目标锁定在贪心算法。熟悉蓝桥杯真题分布的朋友都清楚贪心不算高频压轴但它几乎是每年必考的中等难度题而且常常和排序、Java集合类、双指针组合在一起出现作为省赛拿分的关键题型。为什么单独拿出一天来啃贪心因为这类题有个特点题目读起来简单代码写起来也短但怎么想这一步非常容易卡壳。很多朋友刷题时会遇到这种情况——拿到题觉得有思路随手写了一版样例过了交上去只能过一半测试点剩下全部超时或者WA。这就是典型的贪心策略没找对或者压根没意识到这题该用贪心。这篇笔记主要聊清楚三件事贪心的本质是什么、赛场上怎么快速判断一道题能不能用贪心、以及几类蓝桥杯常考贪心模型的代码怎么写。适合正在系统备赛蓝桥杯Java组、尤其目标是省二及以上的朋友参考。2. 贪心思想拆解为什么局部最优能推出全局最优2.1 从生活场景理解贪心的本质先别急着看题。我习惯把算法映射到生活里理解透了再coding会顺很多。想象一个场景中午吃饭食堂窗口排队每个人打饭时间不一样窗口只有一个怎么安排顺序让所有人排队等待的总时间最短直觉告诉你把打饭时间短的人排在前面。这就是贪心——每一步都让当前队伍里的局部等待时间最少最终全局等待时间也最少。但这里有个坑贪心不是所有问题都好使。还是排队场景如果目标从总等待时间最短变成让每个同学等待时间的方差最小那简单按时间排序就不一定对了。所以贪心的本质是在每一步做决策时只考虑当下最优不回头、不回溯赌的是局部最优的累积必然等于全局最优。这个性质在算法里叫贪心选择性质加上最优子结构是判断一题能否用贪心的两条金标准。蓝桥杯的题绝大多数不会为难你去证明这两条但你要能凭直觉感知到。2.2 赛场上判断贪心的四条线索很多人问怎么知道这题贪心能做我总结了一个快速筛查列表按顺序问自己四个问题题目要求最大、最小、最多、最少而且每一步选择的结果不受后续步骤影响即选择了就定了。数据范围很大明显不能用DFS回溯、状态压缩DP去搜全部方案。比如n到10^5级别O(n^2)都勉强通常就是贪心或排序后O(n)扫一遍。题目素材可以抽象成若干个可排序的单元比如线段、任务、物品、数字位排序之后能明显看出某种单调性。尝试构造两三个复杂点的反例发现找不到能推翻当前策略的例子。这四个条件同时成立时这题用贪心的成功率极高。2.3 贪心题三板斧排序、模拟、证明我做贪心题总结出一套固定流程比赛时也这么走至少不会慌。第一板斧找排序维度。80%的贪心题都需要先排序但排序的键是什么非常关键。有的是按结束时间排有的是按价值重量比排有的是按字符串拼接后字典序排。排序错了后面全错。第二板斧写模拟循环。贪心一般不涉及复杂的递归回溯就是for循环/while循环不断取当前最优。这时候注意用Java自带的排序接口Comparator避免手写冒泡排序浪费时间。第三板斧验证正确性。蓝桥杯的题不需要严谨的数学证明但至少要举几组边界测试数据自己测一下尤其注意全0、全1、越界、极端大小值。3. 蓝桥杯Java组贪心高频题型与模型解析3.1 删数问题模型从数字串中删K位求最小结果这题在蓝桥杯里出现过变体也是很多算法教材里的经典。题目大致是给定一个由数字组成的字符串删掉其中K位让剩下的数字串组成的整数最小。很多人第一反应是删最大的数字试一下1432K1删4得到132看着没错。但换成14329K1如果删9得到1432可实际上删掉4得到1329更小。所以删最大是错的。正确的贪心策略是从左往右扫只要当前数字比下一位数字大就立刻删掉当前这个。为什么因为数字的大小取决于高位高位的数字越小整个数字越小。所以我们要尽可能让高位变低。用Java实现时最优雅的方式是用双端队列或者栈来模拟import java.util.ArrayDeque; import java.util.Deque; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String num sc.next(); int k sc.nextInt(); sc.close(); DequeCharacter stack new ArrayDeque(); for (char c : num.toCharArray()) { while (!stack.isEmpty() k 0 stack.peekLast() c) { stack.pollLast(); k--; } stack.offerLast(c); } // 如果还没删够K位从尾部继续删 while (k 0 !stack.isEmpty()) { stack.pollLast(); k--; } // 去掉前导零 StringBuilder sb new StringBuilder(); boolean leadingZero true; for (char c : stack) { if (leadingZero c 0) { continue; } leadingZero false; sb.append(c); } System.out.println(sb.length() 0 ? 0 : sb.toString()); } }这个代码有几个细节值得注意。Deque用了pollLast和offerLast相当于把双端队列当栈用删除K位的循环条件是k 0删够了就直接追加前导零要用布尔标记跳过否则会输出空字符串。这道题我当年刷的时候踩过一个坑删完K位之后剩下的尾部数字可能还是比前边大比如12345K2整个串是递增的前面的循环一次都不删最后就必须从尾部删。很多新手只写前半段交上去结果就不对。这也是为什么代码里有一个单独的尾部删除循环。《--这段对比可以删掉保留实现即可--》3.2 区间选点与区间覆盖模型按右端点排序的套路区间类是蓝桥杯贪心题第一大热门几乎每年都有影子。核心就两种一是区间选点在若干区间里选最少的点使每个区间都至少包含一个点二是区间覆盖用最少区间覆盖一段总长度。先看区间选点的经典做法把所有区间按右端点从小到大排序然后依次选右端点作为点只要下一个区间的左端点在上一个选择的点之后就再选它的右端点。import java.util.Arrays; import java.util.Scanner; class Segment implements ComparableSegment { int left, right; Segment(int left, int right) { this.left left; this.right right; } Override public int compareTo(Segment o) { return this.right - o.right; } } public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); Segment[] segs new Segment[n]; for (int i 0; i n; i) { segs[i] new Segment(sc.nextInt(), sc.nextInt()); } sc.close(); Arrays.sort(segs); int count 0; int lastPoint Integer.MIN_VALUE; for (Segment s : segs) { if (s.left lastPoint) { lastPoint s.right; count; } } System.out.println(count); } }关键点在于为什么按右端点排而不是左端点。直观理解右端点越小说明这个区间越着急被覆盖尽早覆盖它最有利而且把点选在尽量靠右的位置可以顺带覆盖更多的后续区间。区间覆盖问题则是另一个方向给定总区间[L, R]给你一堆小区间问最少用几个能完全覆盖。它的排序方式是按左端点排序从左往右扫每次在能够覆盖当前起点的区间里挑右端点最大的那一个。注意是当前起点起点会随着选中的区间向右更新所以循环嵌套扫描时要用临时变量记录最远能到哪。这两种区间题在蓝桥杯的真题里经常被包装成种树、灌溉、雷达安装这些生活化背景但剥掉壳子就是同一个模型。我建议刷题时直接把壳子脱掉归类到区间模型里去套模板。3.3 比值贪心模型性价比排序与分数背包还有一种常见的贪心模型是性价比思想典型例子是分数背包问题物品可以分割背包容量有限怎么拿能让总价值最大策略当然是优先拿单位重量价值最大的物品。我拿蓝桥杯风格的题举个例子一个容器容量为M有若干种饮料每种饮料有自己的总量和总甜度问最多能装多少总甜度。注意和0-1背包的区别饮料可以倒一部分取部分是合法的所以用贪心不能用DP。import java.util.Arrays; import java.util.Scanner; class Drink implements ComparableDrink { int volume; int sweetness; Drink(int volume, int sweetness) { this.volume volume; this.sweetness sweetness; } Override public int compareTo(Drink o) { double r1 (double) this.sweetness / this.volume; double r2 (double) o.sweetness / o.volume; return Double.compare(r2, r1); // 降序 } } public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int M sc.nextInt(); int n sc.nextInt(); Drink[] drinks new Drink[n]; for (int i 0; i n; i) { drinks[i] new Drink(sc.nextInt(), sc.nextInt()); } sc.close(); Arrays.sort(drinks); double ans 0; for (Drink d : drinks) { if (M 0) break; int take Math.min(d.volume, M); ans (double) take * d.sweetness / d.volume; M - take; } System.out.printf(%.2f\n, ans); } }这类题反复出现的原因是它考察的不仅是排序还考察你能否识别出部分取用的场景。如果用0-1背包去套分数背包复杂度O(nM)直接超时而且结果也不对。所以做题前先判断物品能不能分割这是贪心和DP的分水岭。4. 实操记录三道改编题的完整跑通过程4.1 题一删数问题的完整调试我按照上节的代码跑了一道测试输入14329K1预期输出1329。手动走一遍循环读入4和1比较4比1大但此时栈空直接入栈读到3栈尾是44比3大删除4k变成0把3入栈后面依次入栈2、9。最终栈内是1 3 2 9输出1329符合预期。再测一组边界100200K1。从左往右看1比0大删除1输出00200去掉前导零后是200。检验一下是不是最小——100200删除一位可能的结果有00200、10200、10020、10020、10020最小确实是200。这么一测就发现删最大数的直觉错得有多离谱删1才是对的。调试这类题时还要注意K可能等于数字长度或者大于长度。代码里最后的st.isEmpty()判断会出现输出直接是0这个分支一定要写上否则数组越界或者输出空串。4.2 题二活动安排问题区间调度完整实现这道题在蓝桥杯中出现的频率极高。简单描述一天内有n场活动每场有开始时间和结束时间你一个人最多能参加几场不重叠的活动经典贪心策略是按结束时间排序优先选择结束时间早的。import java.util.Arrays; import java.util.Scanner; class Activity implements ComparableActivity { int start, end; Activity(int start, int end) { this.start start; this.end end; } Override public int compareTo(Activity o) { return Integer.compare(this.end, o.end); } } public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); Activity[] acts new Activity[n]; for (int i 0; i n; i) { int s sc.nextInt(); int e sc.nextInt(); acts[i] new Activity(s, e); } sc.close(); Arrays.sort(acts); int ans 0; int currentEnd -1; for (Activity a : acts) { if (a.start currentEnd) { ans; currentEnd a.end; } } System.out.println(ans); } }这个代码的核心判断是a.start currentEnd。注意如果活动可以在结束后立刻开始下一场用如果要求严格错开用。蓝桥杯的题意描述一般会写清楚可以在结束的同一时刻开始另一场审题时多看一眼。时间复杂度的分析也不难排序O(n log n)扫描O(n)整体O(n log n)在n10^5甚至10^6时都能轻松跑过。4.3 题三多机调度问题的起点蓝桥杯可能考到多机调度的简化版有n个任务每个任务需要一定时间有k台相同的机器怎么把任务分配给机器让总完成时间最短。这个模型没有上面那些题那么标准我见过一个常见贪心策略是优先把耗时长的任务分配给当前负载最少的机器也就是最长处理时间优先LPT。但注意LPT并不保证全局最优它是近似算法在蓝桥杯题里通常会设置成任务数大于机器数、且任务时间可排序这种特殊情况此时用堆来维护每台机器的当前负载。import java.util.Arrays; import java.util.Collections; import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int k sc.nextInt(); Integer[] tasks new Integer[n]; for (int i 0; i n; i) { tasks[i] sc.nextInt(); } sc.close(); Arrays.sort(tasks, Collections.reverseOrder()); PriorityQueueInteger pq new PriorityQueue(); for (int i 0; i k; i) { pq.offer(0); } for (int t : tasks) { int cur pq.poll(); pq.offer(cur t); } int ans 0; while (!pq.isEmpty()) { ans Math.max(ans, pq.poll()); } System.out.println(ans); } }这道题我之所以放进实操是因为它提醒大家贪心题的难点不在写代码在识别出这题其实是你学过的哪种模型。多机调度里维护最小堆这一步很多选手能想到分配任务但想不到要用堆实时获取最少负载的机器。5. 常见问题与排查技巧实录5.1 排序方向搞反样例都过不了区间选点问题按左端点还是右端点排序网上说法很多。我最开始也记混过。一个好记的方法如果题目的约束是区间的右边界尽量小就按右端点排序如果约束是覆盖的起点不断向右推进就按左端点排序。实战里怎么验证排序方向对不对构造两个区间[1,5]和[2,3]。如果按左端点排先处理[1,5]选了右端点5那么[2,3]没被覆盖需要再选一个点总数是2如果按右端点排先处理[2,3]选3[1,5]包含3总数是1。答案明显是1所以按右端点排是对的。5.2 贪心反例不直观试用三种输入验证刷贪心题最容易出问题的是自认为策略正确但一提交过不了大数据。我的对策是给自己出三组测试第一组是题目样例第二组是极端边界比如区间为空、数字全是0、任务时间全都一样第三组是精心构造的反例。拿删数问题来说我故意输入889K1看看会不会输出89。再输入999K2看会不会输出9。这种极端输入能暴露出循环退出条件的错误。5.3 Java实现贪心时容易忽略的API细节Java组刷题时要特别注意Comparator和Comparable的不同。Comparable是类内部实现排序规则Comparator是外部单独写比较器。刷题时我更推荐直接在类上实现Comparable代码更紧凑省得写匿名内部类。另一个高频坑是Integer.MIN_VALUE用错。区间端点可能有负数用0初始化当前指针会出错应该用Integer.MIN_VALUE或者直接根据题意用一个足够小的数。PriorityQueue默认是小顶堆如果要用大顶堆需要传入Collections.reverseOrder()。贪心里的取最大和取最小非常依赖堆的用法多机调度那道题里如果忘了传反转比较器结果就直接反了。5.4 时间复杂度的取舍到了备赛后期很多朋友贪心会过度思考。举个例子区间选点如果加一个限制每个点只能覆盖有限个区间就不能简单贪心了可能得考虑差分数组二分答案这类技巧。这时如果还是一味套贪心模板复杂度没问题但结果错如果怀疑是不是贪心做不了回去写DP又超时。判断方法其实简单先看题目要求的答案是不是一个策略性结论再看能不能构造反例。只要能构造出反例就果断换思路。我一般给自己限制最多10分钟验证反例验证不出来就用贪心写写完了多测几组数据后再决定是否推翻。5.5 读题时留意隐藏条件的表述蓝桥杯的贪心题经常在题意里加一些温柔陷阱。比如活动安排里写同一天最多能参加多少场那么结束时间等于开始时间的活动可不可以参加如果题目没说默认是可以同时段的用比较如果说了不能同时就要改成。删数问题里问剩余的数字最小但如果题目要求剩余数字的位数必须保持K位删除之后的所有位数那前导零就不能随便删要看清输出要求。这类细节失分最可惜因为它不是不会做是审题漏了半句话。6. 刷题顺序建议与备赛节奏6.1 推荐按难度递进的刷题路径如果你刚开始刷贪心我建议按这个顺序来每类都做熟悉了再碰真题最简单的入门是求最大最小类比如最大子段和注意这是DP和贪心的交叉题、最少硬币问题只有可分割时才是贪心、最优装载问题。这些题主要练排序扫描的肌肉记忆。接下来刷区间类把区间选点、区间覆盖、活动安排放在一起做因为它们的排序逻辑相近但细节不同对比着刷记得牢。再往后是字典型/拼接类比如把若干数字拼接成最大数这类题的比较器是(ab).compareTo(ba)很考验对排序规则的理解。6.2 第6天之后的贪心复习策略贪心算法不适合零散刷更适合集中两三天刷完、再通过真题反复巩固。我的做法是每天刷完题把模型关键词记录下来比如右端点排序最大性价比倒序扫数字位下次看到新题先匹配关键词库匹配上了基本就确定用贪心。蓝桥杯省赛的贪心题通常在前5题出现属于必拿分题。如果做到第5题左右发现是贪心千万别慌认真读题套模型一般10分钟就能写出来。6.3 备赛中Java调试技巧对贪心题的加成调试贪心题的代码不要光看输出对不对要打印中间状态。以删数问题为例我在每个元素入栈前打印一下当前栈内容和剩余k值一眼就能看出删除策略是否生效。打印中间变量的技巧在比赛里同样适用但注意提交前删掉调试输出否则直接判编译错误或输出格式错。7. 这几天的备赛回看与经验沉淀到了Day6回看前几天刷的基础题会发现一个事实贪心算法是前面所有排序、Java集合类、时间复杂度的综合演练场。它不要求高深的数学但要求一种不回头的决策胆识。我自己备赛蓝桥杯Java组最大的感受是贪心题能不能做出来不取决于你刷了多少道而取决于你是否能把每一道题拆成排序键选择规则证明反例三步。比如今天做过的删数问题排序键是数字的原始顺序选择规则是删除逆序对中的前一个反例就是删最大数策略。活动安排问题的排序键是结束时间选择规则是尽量选早结束的反例是按开始时间排序的策略。这种拆解习惯一旦养成后面刷DP题也会轻松很多。最后分享一个实战小技巧每道贪心题做完把这题改造成另一种限制条件下的新题再想一遍新策略。比如删数问题如果改成删K位后要求剩余数字最大策略就变成删除逆序对中的后一个如果改成只能从两端取数像窗口取数就又回到了双指针或单调队列。这种举一反三的方法比闷头刷十道新题更管用对比赛时快速识别模型帮助明显。