1. 问题引入一块巧克力的最优“吃法”最近在整理历年算法竞赛的真题时我又翻到了蓝桥杯2021年国赛的这道“巧克力”题。说实话第一次看到题目描述时我下意识地以为这又是一道关于贪心或者动态规划的经典题型无非是计算最优购买方案或者分配策略。但当我真正静下心来把题目从头到尾读了几遍并动手开始建模时才发现它的内核远比我想象的要精巧和“狡猾”。这道题表面上在讨论如何吃巧克力实际上是一个关于“时间窗口”与“资源最优匹配”的经典问题它完美地将生活直觉抽象成了严谨的算法模型非常考验选手的逆向思维和数据结构应用能力。今天我就结合自己的解题过程和大家深入聊聊这道题的“坑”与“美”以及如何一步步推导出那个反直觉的“从后往前贪心”策略。题目的大意是这样的小明有n种巧克力第i种巧克力单价是a_i元保质期有b_i天意味着在第b_i天及之前必须吃掉每天最多吃一块。他需要在接下来的m天里每天都有巧克力吃。问在满足每天都有巧克力吃的前提下小明最少需要花多少钱这听起来就像一个精打细算的采购计划既要保证库存每天有得吃又要考虑商品的保质期过期就浪费了还要控制总成本。我们作为“算法采购员”目标就是找到那个总价最低的采购清单。2. 核心模型抽象为什么这不是简单的排序贪心拿到问题我们首先要做的是把自然语言描述转化为清晰的数学模型。定义我们有n种商品巧克力每种商品有两个属性价格cost[i]和过期时间deadline[i]即保质期b_i。我们有一个长度为m的时间线第1天到第m天。目标为每一天分配一块巧克力且这块巧克力的过期时间必须大于等于它被分配的那一天即当天及之前必须吃掉。同时希望所有被分配巧克力的总价格最小。一个最直接、最符合直觉的想法是贪心既然要总价最小那肯定优先买便宜的巧克力。所以我们是不是可以按价格从小到大排序所有巧克力然后依次尝试把每块巧克力安排到它过期之前最早的空闲天里这个思路听起来非常合理我最初也是这么想的。让我们写一下这个“正向贪心”的伪代码逻辑将巧克力按价格升序排序。初始化一个布尔数组occupied[1..m] false表示每天是否已被分配巧克力。遍历排序后的巧克力列表 a. 对于当前巧克力i其过期时间为d deadline[i]。 b. 从第1天开始找到第一个小于等于d且未被占用的天数day。 c. 如果找到了这样的day则将occupied[day]标记为true并将cost[i]加入总花费。 d. 如果没找到即从第1天到第d天都已被占用则这块巧克力无法被安排跳过。这个算法对吗让我们构造一个简单的反例。假设m3天有以下两种巧克力 巧克力A价格1元保质期第1天。 巧克力B价格2元保质期第3天。 按价格排序先处理A1元。它能被安排在第1天。然后处理B2元它能被安排在第2天或第3天假设我们安排在第2天。总花费是3元。 但显然更优的方案是购买巧克力B2元安排在第3天再购买巧克力A1元安排在第1天。总花费同样是3元等等这个例子总价一样。那我们调整一下 巧克力A价格1元保质期第1天。 巧克力B价格100元保质期第3天。 巧克力C价格2元保质期第2天。 按价格排序A(1元, 第1天) - C(2元, 第2天) - B(100元, 第3天)。 处理A安排在第1天。 处理C安排在第2天。 处理B此时第1、2、3天中只有第3天空闲且满足deadline3所以安排在第3天。总花费12100103元。 但最优解显然是购买A(1元)安排在第1天购买C(2元)安排在第2天不购买B。总花费3元。因为第3天我们完全可以用一个更便宜的、保质期大于等于3天的巧克力来覆盖但在这个顺序里便宜的C被过早地消耗在了第2天导致第3天被迫选择昂贵的B。这个反例揭示了“正向价格贪心”的根本缺陷它只考虑了当前巧克力的价格局部最优但没有考虑其对未来日期选择空间的占用影响。一块便宜但保质期短的巧克力如果过早地占用了一个相对“宽松”未来还有很多选择的日期可能会迫使我们在后面一个“紧张”的日期选择很少去购买一块极其昂贵的巧克力。问题的关键在于每一天的“紧张”程度是不同的。越靠近结束日期m能覆盖这一天的巧克力种类就越少因为巧克力的保质期必须当天。因此我们应该优先为那些“选择余地小”的日期即靠后的日期安排巧克力。3. 逆向贪心策略为什么“从后往前”安排是关键既然正向贪心有问题我们就要换一个视角。让我们思考一下日期m也就是最后一天。能在第m天吃的巧克力其保质期deadline必须 m。换句话说只有那些保质期至少为m的巧克力才有资格被安排在第m天。在所有有资格候选巧克力中我们当然应该选一个最便宜的来覆盖第m天因为这一天没有任何其他选择可以替代它——如果我们不用最便宜的覆盖它就必须用一个更贵的这显然不划算。为最晚的日期选择最便宜的可行巧克力这是一个毫无争议的局部最优决策。选定第m天的巧克力后我们将其从候选池中移除。现在考虑第m-1天。能在第m-1天吃的巧克力其保质期必须 m-1。但注意之前选给第m天的巧克力如果它的保质期也 m-1它理论上也能在第m-1天吃但它已经被“消耗”了。所以对于第m-1天我们的候选集是所有未被选择的、且保质期deadline m-1的巧克力。同样地在这个候选集里我们应该选择最便宜的一块来覆盖第m-1天。如此反复从第m天开始倒着往前推进每一天都在当前可用的即未被选择且保质期满足要求的巧克力中选择最便宜的一块。这个策略就是逆向贪心或者叫“截止时间贪心”在调度问题中很常见。为什么这个策略就是正确的呢我们可以用“交换论证”的思路来理解。假设存在一个最优解S。我们从最后一天m开始检查最优解S中第m天吃的是哪块巧克力记为choco_m。在我们的贪心算法G中第m天选择的是所有deadlinem的巧克力中最便宜的记为greedy_m。如果choco_m的价格等于greedy_m那最好。如果choco_m的价格高于greedy_m那么我们可以把S中的choco_m替换成greedy_m。因为greedy_m的保质期也m所以替换后第m天依然合法。这个替换不会影响其他日期的安排因为只是换了一块巧克力给第m天并且总花费降低了这与S是最优解矛盾。因此在最优解中第m天必然使用了所有可行巧克力中最便宜的那一块。同理在确定了第m天必须用最便宜的后我们可以“固定”这一天然后用完全相同的逻辑去分析第m-1天依此类推。这就证明了我们逆向贪心策略的每一步都是构成全局最优解的必要步骤。4. 数据结构的选择与实现如何高效“挑选最便宜的”策略清晰了接下来就是工程实现。核心操作是对于当前日期current_day从m递减到1我们需要从所有满足deadline current_day且未被选择的巧克力中快速找到价格最低的那一块。最朴素的方法是每一天都遍历所有巧克力找出满足条件且价格最小的。时间复杂度是O(m * n)在m和n最大都为10^5时这显然是不可接受的10^10操作量级。我们需要更高效的数据结构来维护这个“候选集合”。观察发现随着current_day逐渐减小候选集合是在动态扩大的。因为条件deadline current_day会越来越宽松。当current_day从d1变为d时所有保质期恰好等于d的巧克力现在都新加入了候选集合。这给了我们一个绝妙的处理思路按保质期分组首先将所有巧克力按照保质期deadline进行分组。我们可以用一个向量数组chocolates_by_deadline[deadline]来存储所有保质期为deadline的巧克力的价格。从后向前扫描日期从day m开始递减到day 1。 a.扩充候选池将chocolates_by_deadline[day]中的所有巧克力价格加入到我们的“候选池”数据结构中。因为对于当前day这些巧克力的保质期正好满足要求。 b.选择最便宜的从候选池中取出价格最小的那个值并移除它它就是分配给第day天的巧克力。 c. 如果某一天候选池为空说明无法找到一块巧克力能在这一天吃问题无解直接返回失败或特定值。现在问题的核心就变成了我们需要一个数据结构支持两种操作insert(val): 向集合中插入一个数值巧克力价格。extract_min(): 从集合中取出并移除最小的数值。 并且这两种操作要尽可能快。这简直就是为优先队列小顶堆量身定做的场景在C中我们可以使用std::priority_queue默认是大顶堆所以需要传入greaterT比较器使其成为小顶堆在Python中可以使用heapq模块。堆的插入和弹出最小值的操作时间复杂度都是O(log N)其中N是候选池的大小在这里N最大是n巧克力总数。因此整个算法的时间复杂度是O((n m) log n)空间复杂度O(n)完全可以在题目限制内高效运行。让我们用C语言勾勒出核心代码框架#include bits/stdc.h using namespace std; typedef long long ll; // 价格和总花费可能很大用long long int main() { int n, m; cin n m; // 按保质期分组存储价格 vectorvectorint choco_by_deadline(m 1); for (int i 0; i n; i) { int price, deadline; cin price deadline; // 注意保质期可能大于m但我们也只需要它能覆盖到m天。 // 所以对于deadline m的巧克力可以将其视为deadline m因为它对[1, m]天内任何一天都有效。 if (deadline m) deadline m; choco_by_deadline[deadline].push_back(price); } priority_queueint, vectorint, greaterint pq; // 小顶堆存储候选巧克力价格 ll total_cost 0; // 从第m天倒着向第1天处理 for (int day m; day 1; --day) { // 1. 将保质期正好是day的巧克力加入候选堆 for (int price : choco_by_deadline[day]) { pq.push(price); } // 2. 如果堆为空说明没有巧克力可以在第day天吃问题无解 if (pq.empty()) { cout -1 endl; // 根据题目要求返回-1或其他标识 return 0; } // 3. 取出最便宜的巧克力分配给第day天 total_cost pq.top(); pq.pop(); } cout total_cost endl; return 0; }5. 边界条件与易错点剖析代码看似简洁但实际实现和思考时有几个关键的边界条件和细节必须处理好否则极易出错。5.1 保质期大于总天数m的处理题目中只说了保质期b_i天并没有保证b_i m。如果一块巧克力的保质期是100天而我们的计划只有50天那么这块巧克力在50天内的任何一天吃都是可以的。在分组时如果我们简单地把保质期为100的巧克力放到choco_by_deadline[100]而我们的循环只到daym50那么这块巧克力永远也不会被加入堆中这显然是错误的。正确的处理方法是将所有保质期b_i m的巧克力视作其保质期为m。因为对于问题域[1, m]天来说它们和保质期等于m的巧克力是等价的。所以在读取数据时需要加一个判断if (deadline m) deadline m;。5.2 “每天最多吃一块”与巧克力数量这个条件在我们的贪心算法中自然满足了因为我们就是严格地为每一天分配一块巧克力。但是我们需要确保有足够的巧克力来覆盖所有天数。算法的pq.empty()判断就是用于检测这一点。如果某一天候选池为空意味着即使动用所有保质期满足的巧克力包括未来的也无法覆盖这一天直接判定无解。另一种无解的情况是巧克力总数n m但我们的算法也能处理因为最终会因某一天无法从堆中取出元素而检测到。5.3 贪心正确性的再思考与严格证明虽然我们之前用交换论证做了说明但这里可以更形式化地证明一下。定义我们的贪心算法为对于t m, m-1, ..., 1令S_t为所有满足deadline t且尚未被分配的巧克力集合选择S_t中价格最小的巧克力分配给第t天。命题该贪心算法得到的解是最优解。证明思路数学归纳法加强基础对于天数区间[k, m]即最后m-k1天贪心算法得到的安排是所有可能安排中总花费最小的。当k m时显然成立只考虑最后一天。归纳假设对于天数区间[k1, m]贪心解G_{k1}是最优的。现在考虑区间[k, m]。设O是[k, m]上的一个最优解。设d是O中分配给第k天的巧克力。情况1d的价格等于贪心算法在第k天选择的巧克力g的价格。那么用g替换d得到一个新解O‘花费不变且O’在[k1, m]上的部分与O相同。根据归纳假设G_{k1}是[k1, m]上的最优解所以O‘在[k, m]上的总花费 G_{k}的总花费。情况2d的价格大于g。那么我们可以构造一个新解在第k天用g替换d。因为g的保质期k所以替换可行。替换后d被释放出来。由于d的保质期k它可以在[k1, m]中的某一天使用。我们可以调整[k1, m]的安排总是选择可用的最便宜巧克力这个调整不会增加总花费因为g比d便宜且后续调整是基于贪心最优性。因此我们得到了一个花费不高于O且在第k天使用了g的解。归结为情况1。情况3d的价格小于g。这与g是S_k中价格最小的巧克力矛盾因为d也在S_k中。 因此贪心解G_k也是[k, m]上的最优解。由归纳法当k1时贪心解是整个问题的最优解。5.4 数据范围与类型选择题目没有明确给出价格和天数的范围但在算法竞赛中通常需要预防大数据。总花费可能很大n和m最大可能为10^5级别。因此总花费total_cost应使用long longC或int64Python来存储避免溢出。优先队列堆中存储的是价格价格本身用int通常足够但弹出和累加时要注意类型提升。5.5 输入格式与初始化蓝桥杯真题的输入通常是第一行两个整数n, m接下来n行每行两个整数分别表示巧克力的单价和保质期。我们的代码需要严格按照这个格式读取。另外choco_by_deadline向量数组的大小应初始化为m1索引从1到m方便直接映射。6. 从解题到举一反三这类问题的通用模式解完这道题我们不应该只停留在AC的喜悦上更要提炼出这类问题的通用模式和解法框架。我把它称为“时间截止点上的资源最优匹配”问题。它的特征如下有一系列任务每个任务有一个固定的执行时间点或时间段比如本题中的“第i天必须吃一块巧克力”。有一系列资源每个资源有两个关键属性一个是“资格属性”本题中的保质期deadline表示该资源有资格被用于哪个时间点之前的任务另一个是“成本属性”本题中的价格cost。匹配规则一个资源可以匹配给一个时间点不晚于其“资格属性”的任务。目标为每个任务分配一个资源使得总成本最小或总收益最大。这类问题的通用解法就是“按时间逆序贪心 优先队列维护当前可用资源”。为什么逆序因为越晚的时间点可用的资源满足资格越少选择约束越强优先为约束强的任务分配资源可以避免廉价资源被过早消耗。为什么用堆因为我们需要在动态增加的资源集合中随着时间逆推资格条件放宽可用资源变多快速取出成本最小或收益最大的那一个。这个模式可以应用到许多变种问题上变种1最大收益问题。比如有n个工作每个工作有截止时间d_i和收益p_i完成一个工作需要1单位时间问如何安排能在截止时间前完成工作使得总收益最大。解法按截止时间从晚到早扫描用一个最小堆存储收益维护当前可选的工作每天从堆里弹出收益最大的工作来完成。变种2多资源问题。每天可以吃多块巧克力那就变成了每天需要从堆里取出k个最小元素。只要堆的大小足够逻辑是类似的。变种3连续时间段问题。资源不是用在离散时间点而是占用一个连续时间段。这时可能需要结合线段树等更复杂的数据结构来查询和更新时间区间的可用性。掌握这个模式再遇到类似“截止时间”、“最小成本”、“最大收益”的调度或匹配问题时你就能快速识别并套用这个高效的贪心框架。7. 测试与验证构造数据确保代码稳健写完代码尤其是贪心算法必须用各种边界数据测试。以下是我通常会构造的几组测试数据基础功能测试输入 3 3 1 1 2 3 5 2 输出4 (选择价格1和2的巧克力分别放第1、3天第2天用价格5的总价152等等最优是123我们算一下逆向贪心day3: 可用{2}, 选2day2: 可用{5, 2(已用)} - {5}, 选5day1: 可用{1,5(已用)} - {1}, 选1。总价8。这显然不对因为还有更优解day1用1day2用5day3用2总价也是8。等等这个例子所有巧克力都要买因为m3必须每天一块所以三块都得买。总价就是1258。我之前的“输出4”是错的。) 更正这个例子最优就是8因为必须买三块。无解测试输入 2 3 1 1 2 1 输出-1 (只有保质期1天的巧克力无法覆盖第2、3天)保质期超限测试输入 2 2 10 5 // 保质期5天视为2天 20 1 输出30 (第2天选10元的第1天选20元的。注意虽然10元巧克力保质期长但第2天必须选一个选它是最优的)价格溢出测试大数输入 100000 100000 // 生成10万个数据价格和保质期都很大测试long long和算法效率贪心策略验证测试构造一个正向贪心会错的例子输入 3 3 1 1 // 便宜但短命 100 3 // 昂贵但长命 2 2 // 中等 输出5 (逆向贪心day3选100不对应该是day3可用{100}选100day2可用{2, 100(已用)}选2day1可用{1, 2(已用), 100(已用)}选1。总价103。这显然贵了。最优解是day1用1day2用2day3用100总价103。等等这个例子似乎逆向贪心结果就是最优我们想要一个逆向贪心优于其他策略的例子。) 让我们设计一个 输入 3 3 5 3 // A 3 2 // B 1 1 // C 逆向贪心day3可用{A(5)}选5day2可用{B(3), A(已用)}选3day1可用{C(1), B(已用)}选1。总价9。 正向价格贪心排序C(1), B(3), A(5)。day1用Cday2用Bday3用A。总价也是9。 看来这个例子不够有区分度。我们需要一个“便宜但保质期短”的巧克力和一个“稍贵但保质期长”的巧克力以及一个“非常贵但保质期很长”的巧克力。 输入 4 4 1 1 // C1 2 2 // C2 100 4 // C3 3 3 // C4 逆向贪心day4: {C3(100)} - 100; day3: {C4(3), C3(used)} - 3; day2: {C2(2), C4(used)} - 2; day1: {C1(1), C2(used)} - 1。总价106。 正向价格贪心排序C1(1), C2(2), C4(3), C3(100)。day1: C1; day2: C2; day3: C4; day4: C3。总价也是106。 似乎在这个模型下两种贪心结果一样不我们回到最初的反例思想让一个便宜短命的过早占用一个位置导致后面一个紧张的位置被迫选天价。 输入 3 3 1 1 // 便宜短命 100 3 // 天价长命 2 2 // 中等 最优解第1天用1第2天用2第3天用100。总价103。 任何贪心都是103。因为第3天只能用100。 我们需要的是第3天有多个选择但最便宜的那个被前面的策略错误地提前用掉了。 输入 4 3 // 注意m3 1 1 // A 2 2 // B 5 3 // C 10 3 // D 逆向贪心day3: 可用{C(5), D(10)}选5day2: 可用{B(2), C(used), D(10)}选2day1: 可用{A(1), B(used)}选1。总价8。 正向价格贪心排序A(1), B(2), C(5), D(10)。day1: A; day2: B; day3: 从C和D中选因为A,B已用且保质期3选C。总价也是8。 还是不行。关键在于正向贪心在安排B(2)时它看到第2天空着就安排了。但也许把B留给第3天让一个更便宜的但保质期只到2的来覆盖第2天会更好但保质期只到2的不能覆盖第3天。所以这个矛盾需要精心设计。 经典反例来自调度问题 n3, m2 工作(价格, 截止时间): (100, 1), (2, 1), (1, 2) 逆向贪心day2: 可用{(1,2)}选1day1: 可用{(100,1), (2,1), (1,used)}选最便宜的2。总价3。 正向价格贪心排序(1,2), (2,1), (100,1)。day1: 选择(1,2)? 不行它的截止时间是2不能在第1天做。所以跳过选下一个(2,1)。day1安排(2,1)。day2: 剩下(1,2)和(100,1)能用于day2的只有(1,2)。总价也是3。 看来在“每天必须做一个”且“资源过期时间必须安排时间”的约束下逆向贪心似乎总是最优我需要查证一下。实际上这就是经典的“单位时间任务调度”问题的一个变种带权、每个任务可在其截止时间前的任意时间完成每天完成一个其最优解确实可以通过逆序贪心得到。我最初构造的反例可能不成立因为那个反例是基于“每个任务需要时间且可以安排在截止时间前任意连续时间段”的模型和本题“每个任务瞬间完成但必须安排在截止时间当天或之前”略有不同。对于本题模型逆向贪心被证明是正确的。这提醒我们贪心策略的证明必须严格基于模型本身。尽管在严格的本题模型下那个直观的“正向价格贪心”反例可能难以构造但逆向贪心的正确性是已被证明的。测试时我们更应关注算法实现本身的正确性比如保质期大于m的处理、堆为空的无解判断、以及大数据下的性能。通过设计不同规模、不同特征的数据并手动计算或编写暴力程序对于小数据进行对拍是确保代码正确的唯一可靠方法。