蓝桥杯《巧克力》题解：逆向贪心与优先队列的经典应用

1. 问题引入与核心挑战去年备赛蓝桥杯国赛我遇到了《巧克力》这道题它给我留下的印象比很多复杂的图论或动态规划题都要深刻。乍一看题目描述很简单你有若干种不同保质期和价格的巧克力每天需要吃一块如何在满足每天需求的前提下花最少的钱很多同学的第一反应是贪心——每天选最便宜的吃呗。但如果你真这么写大概率只能过部分样例因为这里有一个关键的约束保质期。一块巧克力只能在生产日期后的特定天数内食用这个限制让“每天选最便宜的”这个直觉策略彻底失效。你可能会想那我提前把快过期的便宜巧克力吃了不就行了问题又来了你怎么定义“快过期”如果今天有一块明天就过期的便宜巧克力和一块还有很久才过期但更贵的巧克力你选哪块这个决策会影响未来几天的选择形成一个典型的带时间窗口的优化问题。这道题的精妙之处在于它完美地将生活常识食品保质期管理抽象成了一个可以用经典算法高效求解的模型。它考察的不是冷僻的知识点而是对基础数据结构的深刻理解和灵活应用。我记得当时在考场上不少同学卡在这里试图用复杂的动态规划去枚举状态结果不是超时就是内存超限。实际上这道题的官方解法期望时间复杂度是O(N log N)核心在于逆向思维和一种数据结构的巧妙使用。下面我就结合当时的解题思路和后续的反复打磨把这道题的“里子”和“面子”都讲透让你不仅知道怎么写代码更明白为什么要这么写以及在实际编码中会遇到哪些坑。2. 问题建模与贪心策略的局限性分析我们先来把题目翻译成更清晰的数学模型。假设总共有N种巧克力每种巧克力有三个属性price单价花费。expire_day保质期从第1天开始算在第expire_day天及之前可以食用。stock库存数量。我们需要规划从第1天到第max_expire天所有巧克力中最晚的保质期的每一天选择一块当天可食用的巧克力即巧克力的expire_day 当前日期d目标是总花费最小。一个最直接的错误思路就是正向贪心从第1天开始遍历所有expire_day d的巧克力选择价格最低的食用然后将其库存减1。这个策略为什么不行我们来看一个反例。假设我们有3天需要规划巧克力数据如下巧克力A价格1保质期第3天库存1块。巧克力B价格100保质期第2天库存1块。巧克力C价格100保质期第1天库存1块。正向贪心过程第1天可选的巧克力有A(价格1保质期3)、B(价格100保质期2)、C(价格100保质期1)。选择最便宜的A花费1。A库存变为0。第2天可选的巧克力有B(价格100保质期2)、C(价格100保质期1)。价格相同假设选B花费100。B库存变为0。第3天可选的巧克力只有C(价格100保质期1)但今天已经是第3天C的保质期是第1天已经过期无法食用规划失败。但实际上存在一个更优且可行的方案第1天食用C价格100。虽然贵但它今天之后就要过期了必须今天吃。第2天食用B价格100。同样它第2天后过期。第3天食用A价格1。此时A仍在保质期内第3天。 总花费为 100 100 1 201。而正向贪心在第3天就失败了总花费无穷大或无法完成。这个例子揭示了问题的核心矛盾便宜的商品保质期可能长我们应该尽可能把它们留给后期以应对未来可能没有便宜货的局面而昂贵但即将过期的商品我们必须在其过期前消费掉否则就会浪费未来的选择机会甚至导致任务失败。这就像生活中管理你的冰箱库存快过期的牛奶即使买的时候贵你得先喝而还有很久才过期的罐头可以往后放。所以正确的贪心方向应该是从后往前规划也就是“时光倒流”法。我们从最后一天max_expire开始往前倒着安排每一天的巧克力。对于第d天我们只需要在所有保质期expire_day d的巧克力中做选择。此时因为我们是从后往前安排的对于第d天来说所有保质期满足条件的巧克力它们的“未来”都已经被安排好了第d1天及以后。那么在第d天我们最优的策略就是在所有“可用”的巧克力里选一个价格最低的来消费。因为对于这些可用的巧克力如果今天不用掉其中一块那么它要么会在未来的某天被用掉但未来可能还有更便宜的选择要么就会过期浪费。今天用掉最便宜的那块可以为未来保留相对更贵但仍在保质期内的选择从整体上看是最优的。注意这里的“从后往前贪心”需要严格的证明其正确性通常使用“替换法”或“决策包容性”在算法竞赛中对于此类经典问题有时被称为“过期任务调度”或“带时间限制的贪心”该策略的正确性是公认的。我们的重点在于如何高效实现这个策略。3. 核心数据结构优先队列堆的选型与实现理解了逆向贪心策略接下来就是如何高效实现。对于第d天我们需要执行两个操作加入将所有保质期expire_day d的巧克力加入到“当前可用巧克力集合”中。选择并移除从“当前可用巧克力集合”中选出价格最低的一块巧克力作为第d天的消费并将其从集合中移除库存减1如果库存为0则彻底移除。关键点在于这个“当前可用巧克力集合”需要频繁地进行插入和查询并移除最小值的操作。什么数据结构最适合数组或链表需要O(N)的时间来查找最小值太慢。平衡二叉搜索树如Java的TreeMap可以做到O(log N)但我们需要存储多个价格相同的巧克力库存1并且主要操作是最小值查询和删除。此时优先队列PriorityQueue特别是最小堆Min Heap就成了不二之选。它的特性是插入offer操作的时间复杂度为 O(log N)。获取并移除最小元素poll操作的时间复杂度为 O(log N)。获取最小元素peek操作的时间复杂度为 O(1)。这完美契合了我们的需求。在Java中java.util.PriorityQueue默认就是一个最小堆。实现细节与坑点我们不能简单地把巧克力对象扔进堆里。因为同一种巧克力有多块库存如果每一块都作为一个独立对象插入堆当库存很大时比如10^5对象创建和堆调整的开销会很大。更优雅的做法是我们只关心价格和库存。我们可以定义一个简单的类或直接使用数组但更常见的竞赛做法是将每种巧克力按其保质期分组。具体步骤读入所有巧克力数据按照保质期expire_day进行归类。我们可以使用一个ListInteger[]数组下标表示保质期列表里存放该保质期下所有巧克力的价格。或者使用MapInteger, ListInteger。从最后一天max_day循环到第1天。将当天d到期的所有巧克力的价格加入到优先队列pq中。如果队列不为空则取出队首元素最低价格将其加入总花费ans并将该价格对应的巧克力库存减1这里需要处理库存逻辑。如果队列为空说明没有巧克力可以在第d天食用问题无解。库存处理的技巧我们如何知道取出的这个价格对应的巧克力是否还有库存一个高效的方法是使用HashMapInteger, Integer来记录每个价格当前剩余的库存。当我们从堆里poll出一个价格p时去HashMap里查它的库存stockMap.get(p)。如果stock 1则库存减1总花费加上p。如果stock 1则库存减1后变为0总花费加上p并且这个价格以后不会再被加入考虑因为该种巧克力已耗尽。这里有个关键从堆里poll出价格p后即使它的库存变为0堆里可能还存在其他价格为p的节点来自之前加入的同价格不同保质期的巧克力。所以我们需要在每次从堆顶取元素时进行“清理”操作如果堆顶元素对应的库存已经为0则直接将其poll掉直到堆顶元素的价格对应库存 0 或堆为空。这个过程被称为“延迟删除”或“堆顶清理”。// 伪代码示意核心循环 long totalCost 0; // 使用long防止溢出 int maxDay // 所有巧克力中的最大保质期; PriorityQueueInteger minHeap new PriorityQueue(); MapInteger, Integer priceStock new HashMap(); // 价格 - 剩余库存 // 假设chocolatesByDay是一个ListInteger[]chocolatesByDay[d]存放第d天到期的巧克力价格列表 for (int day maxDay; day 1; day--) { // 1. 加入当天到期的巧克力 if (chocolatesByDay[day] ! null) { for (int price : chocolatesByDay[day]) { minHeap.offer(price); priceStock.put(price, priceStock.getOrDefault(price, 0) 1); } } // 2. 为这一天选择一块巧克力 if (minHeap.isEmpty()) { // 无解处理 System.out.println(-1); return; } // 清理堆顶无效元素库存为0的价格 while (!minHeap.isEmpty() priceStock.get(minHeap.peek()) 0) { minHeap.poll(); } // 取出有效的最低价 int cheapestPrice minHeap.poll(); totalCost cheapestPrice; // 更新库存 int newStock priceStock.get(cheapestPrice) - 1; priceStock.put(cheapestPrice, newStock); // 注意这里不需要把cheapestPrice加回堆里因为它已经被消费掉了 } System.out.println(totalCost);4. 算法流程的完整实现与代码剖析结合上面的分析我们来构建完整的Java解决方案。我们会处理输入、数据结构初始化、核心贪心循环以及无解判断。第一步输入处理与数据结构初始化题目通常的输入格式是先输入巧克力种类数n然后n行每行包含价格a、保质期b、库存c。我们需要找到最大的保质期maxExpire来作为循环的终点。同时为了方便按天加入巧克力我们使用一个ListPair数组其中Pair可以是一个简单的对象包含价格和库存。但更紧凑的做法是由于同一天到期的、价格相同的巧克力可以合并库存我们可以使用MapInteger, Long来存储键是价格值是库存数量。不过为了简化我们也可以用一个ListInteger数组但每个价格根据库存添加多次对于大数据量这可能效率较低但代码简单。在竞赛中如果库存数量不大后者是可以接受的。这里我们采用更高效的按价格合并库存的方式。import java.util.*; public class Main { static class Chocolate { int price; int expire; long stock; // 使用long库存可能很大 public Chocolate(int price, int expire, long stock) { this.price price; this.expire expire; this.stock stock; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); ListChocolate[] chocolatesByDay new ArrayList[200005]; // 假设最大天数根据题目调整 for (int i 0; i chocolatesByDay.length; i) { chocolatesByDay[i] new ArrayList(); } int maxDay 0; for (int i 0; i n; i) { int price sc.nextInt(); int expire sc.nextInt(); long stock sc.nextLong(); maxDay Math.max(maxDay, expire); // 将巧克力信息按保质期分组存放 chocolatesByDay[expire].add(new Chocolate(price, expire, stock)); } // 核心数据结构 PriorityQueueInteger minHeap new PriorityQueue(); // 记录每个价格当前的剩余库存 MapInteger, Long stockMap new HashMap(); long totalCost 0; boolean possible true; // 逆向贪心 for (int day maxDay; day 1; day--) { // 1. 加入当天到期的所有巧克力 for (Chocolate choco : chocolatesByDay[day]) { minHeap.offer(choco.price); stockMap.put(choco.price, stockMap.getOrDefault(choco.price, 0L) choco.stock); } // 2. 为第day天选择一块巧克力 if (minHeap.isEmpty()) { possible false; break; } // 清理堆顶无效库存为0的元素 while (!minHeap.isEmpty() stockMap.get(minHeap.peek()) 0) { minHeap.poll(); } if (minHeap.isEmpty()) { possible false; break; } int chosenPrice minHeap.poll(); totalCost chosenPrice; // 更新库存 long newStock stockMap.get(chosenPrice) - 1; stockMap.put(chosenPrice, newStock); // 重要如果库存还有剩余这个价格可能在未来再次成为候选但不需要重新入队 // 因为它在堆中已经存在可能有多个重复价格节点或者我们采用其他策略 // 实际上由于我们只poll了一个节点堆中可能还有相同价格的节点。 // 如果库存变为0后续的清理步骤会将其移除。 } if (possible) { System.out.println(totalCost); } else { System.out.println(-1); } sc.close(); } }第二步核心循环的逐日解析让我们仔细跟踪某一天d的操作。假设d 5maxDay 10。chocolatesByDay[5]中存放着所有在第5天到期的巧克力信息价格和库存。循环将这些巧克力的价格加入minHeap并在stockMap中累加对应价格的库存。然后代码尝试为第5天选择巧克力。它先清理堆顶那些在stockMap中库存为0的价格这些是之前被消费完的。接着取出堆顶价格假设是3总花费加3并将价格3的库存减1。进入下一天d4的循环。注意堆里仍然保留着之前加入的所有价格包括那些保质期大于5的。当d4时我们只加入expire4的巧克力。这样堆中始终维护着所有“在当前日期及之后仍然有效”的巧克力价格集合。第三步复杂度分析与边界条件时间复杂度每个巧克力价格最多被加入堆一次每次加入和取出都是O(log M)其中M是堆的大小最大为所有不同价格的数量最坏情况是O(N log N)。遍历天数需要O(maxDay)通常maxDay与N同数量级或由题目给出上限。因此总复杂度约为O(N log N maxDay)可以接受。空间复杂度chocolatesByDay数组需要O(maxDay)的空间堆和Map需要O(N)的空间。边界条件库存为0的处理如上所述必须清理堆顶无效元素否则会取到库存为0的价格。总花费溢出总花费可能非常大必须使用long类型存储。无解判断如果在任何一天清理后的堆为空则说明没有巧克力可供当天食用直接输出-1。最大天数需要准确求出所有巧克力中的最大保质期作为循环终点。如果从题目给定的一个固定最大天数比如100000开始循环在前期可能有很多天空循环但通常也能接受。5. 常见错误与调试技巧在实际实现时即使思路正确也很容易掉进一些坑里。下面我总结几个常见的错误点和调试方法。错误1忽略了库存合并导致堆过大或逻辑错误如果对同一种价格、同一天到期的巧克力你不合并库存而是将每一块都作为一个独立的Integer对象插入堆中当库存c很大时例如10^5堆的节点数会爆炸导致内存超限或时间超时。正确的做法是像上面那样用stockMap统一管理库存堆中只存储价格并且同一种价格可以只存储一次尽管我们代码中可能因为多次offer而存在多个相同价格的节点但通过库存清理可以正确处理。错误2没有进行堆顶清理这是最隐蔽的错误。假设一种巧克力价格是5库存有3块。我们第一次poll()出价格5库存减为2。第二次poll()时堆顶可能还是5因为堆里可能有多个价格为5的节点我们再次消费库存减为1。第三次同理库存减为0。问题来了当库存变为0后如果堆里还有价格为5的节点可能来自其他批次下一次循环清理堆顶时会发现stockMap.get(5) 0就会将其poll()掉。但如果你没有清理步骤下一次可能又会poll()出5此时去stockMap里减库存就变成了-1逻辑完全错误。所以while循环清理堆顶是必不可少的。错误3循环的起始和终止条件一定要从maxDay循环到1不能从1到maxDay。这是贪心策略的基础。另外循环的终止条件是day 1确保每一天都被规划到。调试技巧构造小数据测试像前面提到的反例就是最好的测试数据。输入数据少可以手动模拟算法过程验证结果。打印中间状态在循环内打印day堆的大小minHeap.size()堆顶元素以及stockMap的内容可以帮助你清晰地看到每一天的决策过程快速定位是加入、选择还是清理环节出了问题。测试边界数据只有一种巧克力库存足够覆盖所有天数。巧克力保质期全部为1测试逆向贪心是否退化为简单的每天选最便宜的但库存要够。最大天数很大但巧克力种类很少测试循环效率。总花费超过int范围的数据测试是否使用了long。使用对拍器如果你有一个暴力但正确的算法比如深度优先搜索枚举仅适用于极小数据可以随机生成小规模数据对比你的优化算法和暴力算法的结果这是发现逻辑错误最有效的方法之一。6. 算法扩展与同类问题联想解决了《巧克力》问题我们掌握了一种解决“带时间限制的资源调度”问题的通用思路逆向扫描时间线并用优先队列维护当前可用的最优资源。这个模型可以应用到许多变体问题上。变体1任务与收益有n个任务每个任务有一个截止时间d_i和收益p_i。每个单位时间只能做一个任务任务必须在截止时间前完成。如何选择任务使得总收益最大这就是经典的“任务调度最大收益”问题。解法几乎一模一样将任务按截止时间排序从大到小逆向扫描时间用一个最小堆维护当前可做的任务的收益每天每个时间单位从堆里取出收益最大的任务来执行。这里堆要换成最大堆PriorityQueueInteger(Collections.reverseOrder())。变体2会议室安排 II给你一个会议时间安排的数组每个会议有开始时间start_i和结束时间end_i问至少需要多少间会议室。这个问题可以转化为沿着时间线扫描遇到会议开始就需要一间会议室资源遇到会议结束就释放一间会议室。我们需要知道在任何时间点同时进行的会议的最大数量。这可以用一个最小堆来维护正在进行的会议的结束时间。当新会议开始时如果堆顶最早结束的会议的结束时间 新会议的开始时间说明有会议室空出来了可以复用否则就需要新的会议室。变体3库存管理与促销商店有n种商品每种商品有保质期和成本。未来m天每天有一个促销活动当天售出的商品利润更高。你可以在保质期内的任意一天出售商品但每天只能卖一种商品的一个单位。如何安排出售顺序使得总利润最大这可以看作是《巧克力》问题的“利润最大化”版本同样可以使用逆向贪心优先队列最大堆来解决。掌握这个模式后当你再看到“时间”、“截止日期”、“选择”、“最优”这些关键词时就应该立刻联想到逆向扫描和堆这个组合拳。它之所以强大是因为它将一个看似复杂的全局优化问题分解成了每一天的局部最优选择而逆向的顺序保证了局部最优能导向全局最优。7. 竞赛实战中的优化与取舍在蓝桥杯等竞赛环境中除了算法正确性我们还需要考虑代码的运行效率和实现的简洁性。针对《巧克力》这道题我们可以做以下优化和取舍优化1使用数组替代Map存储库存HashMap虽然方便但常数开销比数组大。如果题目中巧克力的价格范围不大比如价格在1到10^4之间我们可以直接用一个long[] stockArr new long[10001]数组来存储库存下标就是价格。这样查询和更新库存的操作就是O(1)比HashMap.get和put更快。判断堆顶价格是否有效就变成了while (!heap.isEmpty() stockArr[heap.peek()] 0)。优化2更紧凑的数据分组我们之前用ListChocolate[]按保质期分组。如果巧克力种类n很大10^5但保质期范围maxDay也很大10^5这个数组是合理的。如果内存特别紧张可以考虑先读取所有数据然后按照保质期进行排序再用一个指针在逆向扫描时按顺序加入堆避免使用巨大的数组。但通常题目给出的内存是足够的。优化3输入输出加速Java的Scanner在读取大量数据时比较慢。可以使用BufferedReader和StringTokenizer来加速输入使用PrintWriter或StringBuilder来加速输出。这在数据量达到10^5级别时效果明显。BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); // ... 后续使用 st.nextToken() 读取取舍代码可读性与性能在竞赛中有时为了快速写出正确的代码牺牲一点性能换取更高的可读性和更低的出错率是值得的。例如使用HashMap比用数组管理库存更不容易出错无需考虑价格范围。除非你确信性能是瓶颈否则可以先写出清晰正确的版本。在时间充裕的情况下再考虑替换为更高效的数据结构。一个更高效的最终版本示例使用数组存库存假设题目保证价格price 10000。import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); // 最大天数根据题目预估这里假设不超过200000 Listint[][] groups new ArrayList[200002]; for (int i 0; i groups.length; i) groups[i] new ArrayList(); int maxDay 0; for (int i 0; i n; i) { st new StringTokenizer(br.readLine()); int price Integer.parseInt(st.nextToken()); int expire Integer.parseInt(st.nextToken()); long stock Long.parseLong(st.nextToken()); // 注意库存可能很大 maxDay Math.max(maxDay, expire); groups[expire].add(new int[]{price, (int)Math.min(stock, 200000L)}); // 库存太大可特殊处理这里简单截断 } PriorityQueueInteger heap new PriorityQueue(); long[] stockOfPrice new long[10001]; // 价格上限为10000 long totalCost 0; for (int day maxDay; day 1; day--) { // 加入当天到期的 for (int[] item : groups[day]) { int price item[0]; long stock item[1]; heap.offer(price); stockOfPrice[price] stock; } if (heap.isEmpty()) { System.out.println(-1); return; } // 清理堆顶 while (!heap.isEmpty() stockOfPrice[heap.peek()] 0) { heap.poll(); } if (heap.isEmpty()) { System.out.println(-1); return; } int chosenPrice heap.poll(); totalCost chosenPrice; stockOfPrice[chosenPrice]--; } System.out.println(totalCost); } }这个版本使用了Listint[][]分组用long[]数组管理库存效率更高。注意处理库存stock可能非常大的情况这里简单做了截断严谨的做法可能需要用long存储并在stockOfPrice数组中使用long但Java数组不支持泛型long[]是OK的。如果价格范围也很大数组方法就不适用了还是得回到HashMap。写完代码通过样例后最好再自己构造几组极端数据测试一下比如所有巧克力保质期都是同一天或者价格全部相同但保质期不同确保逻辑的鲁棒性。这道题在国赛中出现考察的就是选手在压力下能否迅速识别模型、选择合适数据结构并处理好边界条件的能力。多练习这类问题对于提升竞赛水平大有裨益。