第一次看到“HJ165 小红的优惠券”这个标题很多人的第一反应是“这不就是一道模拟题吗把优惠券按价格排序然后算一算”。真上手以后才会发现这道题的精髓根本不是模拟而是隐藏在“优惠券”这个生活场景后面的连续区间覆盖和贪心证明。我最初就是拿递归全排列去硬解小数据没问题一旦优惠券数量到了几百张栈直接炸穿改成 0/1 背包又面临总和过大的问题直到把排序、前缀和和区间扩张这三个词串起来才算真正把这道题吃透。这篇不是题目答案搬运而是以一个刷题老手的视角拆解这道题背后的逻辑、实现细节和避坑经验适合正在准备机试、笔试或者想练贪心思维的同学参考。1. 题目拆解与核心考点分析1.1 生活场景到算法模型优惠券问题在生活中很常见手里有一堆券每张有一个面额每张只能用一次能不能凑出某个订单金额或者凑不出哪些金额。这类题把场景包装成“小红有一堆优惠券问她最凑不出来的金额是多少”本质上就变成了一个组合优化问题。如果把“是否使用某张券”看成二进制的选与不选那么问题就是经典的 0/1 子集和问题。子集和问题最朴素的做法是枚举所有子集复杂度是 2 的 N 次方显然不是正解。但优惠券面额之间有一个非常重要的关系它们共同构造的“可表示金额集合”并不是散乱无章的而是从 1 开始的一段连续区间加上若干零散的点。这道题真正考察的地方就是你能不能发现“连续可表示区间”这个结构并用排序后的线性扫描把它算出来。1.2 三个常见变体同一个“小红优惠券”外壳下题库里常见的考法其实有三种解法也完全不同变体一求最小无法凑出的金额。核心是排序 连续区间扩展时间复杂度 O(N log N)空间 O(1)这是最容易超纲的一版。变体二给定目标金额问能否刚好凑出。这是标准的 0/1 背包可行性问题用一维滚动数组解决复杂度 O(N * target)。变体三给定目标金额问最少用几张券凑出。这是 0/1 背包求最小值初始化为无穷大逐张更新难度比变体二稍微高一点。HJ165 这个编号下最经典、最容易被当成大题的版本通常是变体一。题目会给你一个长度为 N 的数组代表优惠券面额要求输出“不能用这些券凑出来的最小正整数”。很多人一看到“能不能凑出某个数”就条件反射去写背包结果发现目标金额可以达到 10 的 9 次方直接懵掉。这就是没有先做题型识别。1.3 为什么值得花时间刷这道题之所以是一道好题是因为它用非常简单的题干把“证明题”和“编码题”结合在了一起。贪心思路很多人都能猜到但“为什么排序后遇到第一个大于当前可覆盖范围加一的券就立刻能确定答案”这一点需要严格的数学推导。面试或机试的判分点很大程度上也在看你有没有能力把这个理由讲清楚。另外这道题的空间优化也很有意思。即使不用贪心纯 DP 想优化到能通过大范围数据也需要用 bitset 或前缀和技巧。但一旦想通了连续区间合并整个代码就只有十行左右这恰恰是面试官最爱看到的“把复杂问题简化成数学结论”的能力。所以这道题不仅是“HJ165”这一个编号的问题它背后代表了一类区间覆盖题的通用解。2. 核心思路排序 前缀和的“连续金额区段”2.1 核心性质区间扩张用一个例子来建立直觉。假设现在已经能用手中优惠券凑出 1 到 5 的所有整数金额现在又来了一张面额为 4 的券。由于 1 到 5 里每一个金额都已经可达那么“4 已可达的任意金额”就能得到 415 到 459 的所有金额。原来的 1 到 5 和新的 5 到 9 一合并整体就变成了 1 到 9。也就是说只要新面额 v 不超过当前连续区间的右端点加 1那么连续区间就能从“1 到 r”扩展到“1 到 r v”。反过来如果新面额 v 已经大于 r1比如当前已经覆盖 1 到 5新来的券面额是 7那么 7 和原有券的组合只能覆盖 8 到 12 这样跳跃的点区间里仍然有一个空洞“6”。即使后面再来更小的券也已经晚了因为 6 已经无法被凑出来所以最小不可表示金额就是 r1。这个结论是整个题目的基石。严格证明也不复杂。设当前区间为 [1, r]且按面额升序处理。新券面额为 v当 v r 1 时对任意金额 x若 x r旧方案即可覆盖若 x r则考虑 x - v。因为 v r1所以 x - v 的最小值是 1最大值是 rx - v 一定能落在 [1, r] 内。于是“v 旧券组合”能覆盖 (r, rv] 这一段合并后变成 [1, rv]。当 v r 1 时r1 这个金额既不能被旧方案覆盖也不能只用一张新券覆盖因为 v 本身大于 r1。无论后续面额如何r1 都会成为永久的空洞。2.2 为什么不是背包背包解法也能得到最小不可表示金额遍历所有面额更新 dp 数组最后扫描出第一个 false。但这里有一个致命的性能问题dp 数组的长度必须覆盖到所有可能的面额总和。如果 N 是 200每张券面额最大 1000那么总和只有 200000bitset 优化后勉强能过但如果 N 是 10000单张面额达到 10 的 6 次方总和直接来到 10 的 10 次方任何数组都开不下。贪心解法之所以快是因为它不等价于“计算所有可达金额”而是提前根据排序后的面额序列判断第一个缺口出现的位置。仔细想想最小不可表示金额其实只可能出现在“某一张券的面额突然断开连续区间”的地方而不是随机地出现在任意数字上。这就像拼积木只要前面所有小块能拼出完整的 1 到 r那么新来的积木只要长度不超过 r1就不会留下缝隙否则第一个缝隙就出现了。这个性质让问题从“全局搜索”变成了“线性扫描”。2.3 无限使用与一次使用的区别有些相似题型里优惠券是无限量供应的比如“1 元券无限张2 元券无限张”问最少补多少张才能覆盖目标金额。这种情况下只要检测最小面额是否等于 1 即可完全不需要去回溯过去的券。但在 HJ165 这种“每张券只能用一次”的设定里我们不能用无限背包的那一套因为每种面额的库存上限不同可表示范围会被库存数量限制。还有一个容易混淆的题型是“每种面额数量不限但券总张数有限”此时需要统计每一面额的张数再按面额分段处理。相比之下HJ165 的“数组里每张券独立”其实已经相当于给了每张券的数量处理起来更直接。最需要注意的一点是排序后必须一张一张地处理而不是先去重再按面额批量处理否则“同面额有两张券可以凑出更大金额”的情况会被漏掉。3. 从零到一完整实现与关键细节3.1 基础版本代码先给出最核心的 Python 实现。这个版本应对的就是“求最小无法凑出的正整数金额”这一最常见考法。def solve(): import sys data sys.stdin.read().strip().split() if not data: return n int(data[0]) a list(map(int, data[1:1 n])) a.sort() r 0 for v in a: if v r 1: r v else: print(r 1) return print(r 1)代码一共只有十几行核心就是这个if v r 1。我用一个简单例子验证面额数组为 [1, 2, 5]。排序后开始扫描初始 r0v1因为 1 1所以 r 变成 1v2因为 2 2所以 r 变成 3v5因为 5 4所以直接输出 4。这里输出 4 意味着 4 元无法用 [1,2,5] 这三张券凑出来而 1,2,3 都可以。再看一个全覆盖的例子 [1,2,4]扫描完成后 r7循环结束后输出 8表示 1 到 7 都能凑出8 是第一笔凑不出的金额。两个例子都能对得上。3.2 带目标金额的变体实现如果题目不是问“最小凑不出金额”而是直接给一个目标 K问能否凑出 K那就回到 0/1 背包。此时要注意遍历顺序必须倒序否则同一个人张券会被重复使用。def can_make(a, target): dp [False] * (target 1) dp[0] True for v in a: for s in range(target, v - 1, -1): if dp[s - v]: dp[s] True return dp[target]这个做法的复杂度是 O(N * target)target 较小的时候很实用。如果 target 特别大一般会先判断是否能通过贪心快速剪枝先把面额排序如果中间出现了“当前可覆盖范围 1 目标值”且随后又无法突破就可以提前返回 False。把贪心和 DP 结合比无脑跑完整背包要稳得多。还有一个进阶场景目标不是“能否凑出某数”而是“在不超过总金额 M 的前提下最多能凑出多少个不同的金额”。这时仍然可以用连续区间合并的思维但扫描时要额外加一个if r M: break避免不必要的计算。3.3 边界与复杂度复杂度方面排序是 O(N log N)循环是 O(N)整体瓶颈在于排序这在笔试里属于非常优秀的复杂度。空间上只需要常量存储几乎没压力。边界情况尤其要注意几点N0 时没有任何优惠券最小凑不出金额是 1代码直接输出 1。面额包含 0 时0 并不会影响可覆盖的连续区间但要注意读入时不要误把 0 当成干扰项洗掉。面额包含超大数时如果 r 本身已经累加到很大在 Java/C 里要用 long否则 int 会溢出。输入里如果有多组测试用例一定要把 r 重新初始化为 0排序也要在每组数据内部重新执行。4. 实操中容易踩的坑4.1 只想到 DP忽略排序后连续区间合并很多人看到“凑金额”三个字就天然联想到 DP我也是踩过这个坑的。第一次写这道题的时候我用了一个布尔数组去记录所有可达金额然后把每个面额都做一次倒序更新。在小数据里这个做法完全正确一旦把 N 拉到 500面额总和过亿程序直接内存溢出。后来我才意识到这道题不是要你去覆盖整个值域而是要你找“第一个断点”。判断断点不需要知道“面额 100000 能不能凑出来”这种细节只需要关心当前能连续覆盖到的右端点。这就是为什么离线排序 线性扫描是最优解。刷题时候不要被 DP 标签固定住先动手列几个简单样例看看可达金额到底是什么分布再做算法选择。4.2 排序方向弄反排序方向是个很低级但特别容易犯的错。如果按降序排列比如先处理大面额券再处理小面额券会得到错误结论。举个例子面额数组 [3, 1, 2]升序是 [1,2,3]用前面的代码可以得到正确结果 7因为 1 到 6 全覆盖7 无法凑出。但降序是 [3,2,1]处理 3 时当前 r03 1代码会立刻输出 1。这个输出恰恰是错的因为实际上 1 明显可以用面额为 1 的券凑出来。陷入降序陷阱的根本原因是区间扩张依赖“小面额先覆盖低位数字”如果先放大面额低位数字根本没有机会被填充。4.3 边界条件 v r 1 的等号问题“等号”看起来只差一个数字但实际影响非常大。假设当前 r0也就是一张券都没有凑时遇到面额为 1 的券。因为 1 1r 变成 1说明 1 元券可以让可覆盖范围从 0 扩展到 1。如果错误写成了v r 1那么 1 1 不成立程序会直接输出 1相当于漏掉了这第一笔金额。更一般的理解是当 v r1 时新券刚好可以补上当前区间的下一个缺口这时扩展是成立的。比如当前覆盖 1 到 5新券面额 6那么 6 本身就能凑出并且“6 旧券”还能覆盖 7 到 11所以连续区间进一步扩展到 11。等号必须保留这是很多人在笔试中莫名 WA 的原因。4.4 输入输出和数组越界输入读取比想象中更容易出错。有的题目第一行是 N第二行是 N 个整数有的题目第一行是 N 和 M 两个数还有的题目会在后面追加一个测试总数表示多组用例。不能假设格式永远一致。稳妥的办法是先把整行读进来用split()切分再根据第一个数字判断是单组还是多组。数组越界常见于目标金额那一版。如果 target 为 0dp 长度为 1dp[0] 为 True这是正确的。但如果 target 为负数直接报错。因此在写can_make前要加一个if target 0: return False。还有一个细节是面额等于 0 时的内层循环范围从 target 到 0 都是可行的但因为没有价值增长不会造成错误只是白跑一遍。5. 延伸换个场景怎么用5.1 从优惠券到几类面试题把“优惠券”外衣脱掉这道题的骨架可以套进很多其他题目里给定一组砝码重量问不能称出的最小正整数重量。给定一组线段长度问不能用这些线段拼出的最小整数长度。给定一些基础货币单位问在只能使用一次的情况下不能凑出的最小面额。这些场景本质上都是同一个模型一组正整数每个数最多选一次判断从 1 开始连续可表示范围能到哪里。面试时如果能把它们归成一类很多看起来和“优惠券”无关的题就能直接复用 HJ165 的思路。5.2 真实项目里满减、叠加和有效期带来的复杂度现实中电商项目的优惠券远比这道题复杂。真实券可能有“满 100 减 20”这种满减条件也可能有“只能用于特定品类”“不可叠加”“过期作废”等限制。如果你直接把 HJ165 的连续区间结论套到真实系统里多半会出问题因为“满减”引入了订单金额的维度而不是单纯的面额叠加。但在面试场景里出题人故意把真实系统的大量约束剪掉只保留最核心的整数组合逻辑目的就是考察候选人能不能从冗余信息中抽取数学结构。回答时可以提一句“实际系统会额外考虑满减门槛和互斥规则但本题的简化模型等价于 0/1 组合覆盖”这会让面试官觉得你既有工程视野又懂算法本质。5.3 怎么用对照测试做验证如果拿不准自己写的贪心对不对可以写一个暴力程序做对照。暴力思路很简单用子集枚举或 0/1 背包生成一个布尔数组记录所有小于某个上限的可达金额再扫描出第一个 False。把随机生成的面额数组同时喂给暴力程序和贪心程序对比输出是否一致。随机测个一万组只要有一组不一致说明边界没想清楚。我在练习时经常用这个办法它能快速暴露等号条件和排序方向的问题。6. 经验总结与实战心得这道题我用 Java 和 Python 各写过一遍整体感觉是Java 需要注意long类型Python 则要注意输入可能超长导致读取卡顿。实战中我更推荐先用 Python 快速验思路再按目标语言重写因为这里代码实在很短重写成本很低。我个人的心得是做这类区间覆盖题先不要一上来写代码先做三件事——排序、画可覆盖范围、找断点。把 [1,2,5] 这种小例子在手边列一遍比背诵模板管用得多。具体到“HJ165 小红的优惠券”核心结论就一句话升序排序后维护当前连续可覆盖区间右端点 r每次遇到面额 v如果 v r1 就合并区间否则答案就是 r1。最后如果所有券都处理完还找不到断点答案就是 r1。如果你刚开始刷这类题建议把这道题和“POJ 1742 Coins”“经典硬币问题”放在一起对比练习。它们的区别只在于面额是否有数量限制、是否求最小不可表示金额、是否求组合数但底层的 DP 或贪心思想是互通的。把这几道题吃透以后再做优惠券相关题目基本一眼就能看穿出题人想考什么。