第一次看到“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 + 已可达的任意金额”就能得到 4+1=5 到 4+5=9 的所有金额。原来的 1 到 5 和新的 5 到 9 一合并，整体就变成了 1 到 9。也就是说，只要新面额 v 不超过当前连续区间的右端点加 1，那么连续区间就能从“1 到 r”扩展到“1 到 r + v”。
反过来，如果新面额 v 已经大于 r+1，比如当前已经覆盖 1 到 5，新来的券面额是 7，那么 7 和原有券的组合只能覆盖 8 到 12 这样跳跃的点，区间里仍然有一个空洞“6”。即使后面再来更小的券，也已经晚了，因为 6 已经无法被凑出来，所以最小不可表示金额就是 r+1。这个结论是整个题目的基石。
严格证明也不复杂。设当前区间为 [1, r]，且按面额升序处理。新券面额为 v：
- 当 v <= r + 1 时，对任意金额 x，若 x <= r，旧方案即可覆盖；若 x > r，则考虑 x - v。因为 v <= r+1，所以 x - v 的最小值是 1，最大值是 r，x - v 一定能落在 [1, r] 内。于是“v + 旧券组合”能覆盖 (r, r+v] 这一段，合并后变成 [1, r+v]。
- 当 v > r + 1 时，r+1 这个金额既不能被旧方案覆盖，也不能只用一张新券覆盖，因为 v 本身大于 r+1。无论后续面额如何，r+1 都会成为永久的空洞。
2.2 为什么不是背包
背包解法也能得到最小不可表示金额：遍历所有面额，更新 dp 数组，最后扫描出第一个 false。但这里有一个致命的性能问题：dp 数组的长度必须覆盖到所有可能的面额总和。如果 N 是 200，每张券面额最大 1000，那么总和只有 200000，bitset 优化后勉强能过；但如果 N 是 10000，单张面额达到 10 的 6 次方，总和直接来到 10 的 10 次方，任何数组都开不下。
贪心解法之所以快，是因为它不等价于“计算所有可达金额”，而是提前根据排序后的面额序列判断第一个缺口出现的位置。仔细想想，最小不可表示金额其实只可能出现在“某一张券的面额突然断开连续区间”的地方，而不是随机地出现在任意数字上。这就像拼积木，只要前面所有小块能拼出完整的 1 到 r，那么新来的积木只要长度不超过 r+1，就不会留下缝隙；否则第一个缝隙就出现了。这个性质让问题从“全局搜索”变成了“线性扫描”。
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]。排序后开始扫描：
- 初始 r=0；
- v=1，因为 1 <= 1，所以 r 变成 1；
- v=2，因为 2 <= 2，所以 r 变成 3；
- v=5，因为 5 > 4，所以直接输出 4。
这里输出 4 意味着 4 元无法用 [1,2,5] 这三张券凑出来，而 1,2,3 都可以。再看一个全覆盖的例子 [1,2,4]，扫描完成后 r=7，循环结束后输出 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)，整体瓶颈在于排序，这在笔试里属于非常优秀的复杂度。空间上只需要常量存储，几乎没压力。
边界情况尤其要注意几点：
- N=0 时，没有任何优惠券，最小凑不出金额是 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 时，当前 r=0，3 > 1，代码会立刻输出 1。这个输出恰恰是错的，因为实际上 1 明显可以用面额为 1 的券凑出来。陷入降序陷阱的根本原因是：区间扩张依赖“小面额先覆盖低位数字”，如果先放大面额，低位数字根本没有机会被填充。
4.3 边界条件 v <= r + 1 的等号问题
“等号”看起来只差一个数字，但实际影响非常大。假设当前 r=0，也就是一张券都没有凑时，遇到面额为 1 的券。因为 1 <= 1，r 变成 1，说明 1 元券可以让可覆盖范围从 0 扩展到 1。如果错误写成了v < r + 1，那么 1 <= 1 不成立，程序会直接输出 1，相当于漏掉了这第一笔金额。
更一般的理解是：当 v == r+1 时，新券刚好可以补上当前区间的下一个缺口，这时扩展是成立的。比如当前覆盖 1 到 5，新券面额 6，那么 6 本身就能凑出，并且“6 + 旧券”还能覆盖 7 到 11，所以连续区间进一步扩展到 11。等号必须保留，这是很多人在笔试中莫名 WA 的原因。
4.4 输入输出和数组越界
输入读取比想象中更容易出错。有的题目第一行是 N，第二行是 N 个整数；有的题目第一行是 N 和 M 两个数；还有的题目会在后面追加一个测试总数，表示多组用例。不能假设格式永远一致。稳妥的办法是先把整行读进来，用split()切分，再根据第一个数字判断是单组还是多组。
数组越界常见于目标金额那一版。如果 target 为 0，dp 长度为 1，dp[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 <= r+1 就合并区间，否则答案就是 r+1。最后如果所有券都处理完还找不到断点，答案就是 r+1。
如果你刚开始刷这类题，建议把这道题和“POJ 1742 Coins”“经典硬币问题”放在一起对比练习。它们的区别只在于面额是否有数量限制、是否求最小不可表示金额、是否求组合数，但底层的 DP 或贪心思想是互通的。把这几道题吃透，以后再做优惠券相关题目，基本一眼就能看穿出题人想考什么。
