火柴数字问题解析：贪心算法在C++竞赛中的实战应用

1. 问题引入：从火柴棍到数字编码

不知道大家有没有玩过用火柴棍摆数字的游戏？几根小小的火柴，通过不同的排列组合，就能表示出0到9这十个数字。这看似是一个简单的趣味游戏，但在算法竞赛中，它却能衍生出非常考验思维和编程能力的问题。上海计算机学会2021年5月月赛C++乙组的T1题“火柴数字（一）”，正是这样一个将生活趣味与严谨算法结合的典型例子。

这道题的核心是：给定一个整数n，以及每个数字（0-9）所需要的火柴棍数量（题目会给出一个固定的映射关系，比如常见的“标准火柴数字”），我们需要计算出，恰好使用n根火柴棍，能够摆出的最大整数是多少。这里有几个关键约束：摆出的数字不能有前导零；我们必须用完所有的n根火柴，一根不多，一根不少；我们追求的是数值上的最大，而不是位数最多。

乍一看，这有点像我们小时候玩的“用给定钱币凑出最大金额”的问题，但加入了“每个数字成本（火柴数）不同”和“禁止前导零”的复杂条件。它不仅仅考察基本的循环和条件判断，更深入地触及了贪心算法和动态规划的思维边界。很多同学的第一反应可能是用贪心：从最高位开始，尽可能放能摆出的最大数字。这个思路方向是对的，但在“恰好用完”和“处理零”这两个点上，极其容易踩坑。我见过不少实现，跑样例似乎没问题，但一提交就Wrong Answer，问题往往就出在细节处理上。

接下来，我将彻底拆解这个问题。我们会先明确题目给出的“数字-火柴棍”映射规则，这是所有计算的基础。然后，我会带你一步步分析贪心策略为什么是可行的，以及如何严谨地处理那些恼人的边界情况。最后，我们会给出清晰、健壮且高效的C++实现代码，并附上详细的注释和测试用例。无论你是正在备战信奥赛的选手，还是对算法设计感兴趣的开发者，相信这篇深入的分析都能让你有所收获。

2. 问题建模与规则定义

在动手写代码之前，我们必须把问题从自然语言描述转化为精确的数学模型。这是解决任何算法问题的第一步，也是最关键的一步，理解偏差会导致全盘皆输。

首先，题目会给出0到9每个数字所需要的火柴棍数量。这里我们采用最常见的一种“标准火柴数字”摆法，也是许多类似题目（包括国际赛题）的默认设定，其映射关系如下：

我们可以用一个数组来存储这个映射关系，例如int cost[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};。其中cost[i]表示摆出数字i需要的火柴数。

接下来，我们定义问题的输入和输出：

• 输入：一个正整数n，代表总共可用的火柴棍数量。
• 输出：一个正整数，表示恰好使用n根火柴棍能摆出的最大整数。如果无法用n根火柴棍摆出任何一个符合要求的整数（例如n < 2，因为最小的数字1也需要2根火柴），则输出-1。

约束条件分析：

1. 恰好用完：使用的火柴总数必须严格等于n。不能多，也不能少。这直接排除了“小于等于n”这种更简单的背包问题变种。
2. 无前导零：摆出的数字最高位不能是0。例如，n=6时，可以摆出数字0（需要6根），但这是无效的，因为0不是一个正整数（通常题目要求输出正整数）。更重要的是，对于多位数，比如n=12，你不能摆出06这样的数，即使它数值上等于6。你必须确保第一位是1-9中的某个数字。
3. 最大化数值：在满足上述条件的所有方案中，我们需要找到数值最大的那个。注意，数值最大并不直接等同于位数最多。例如，用5根火柴，可以摆出71（3+2=5根，数值71），也可以摆出1（但只用2根，不符合“恰好用完”），或者摆出7（只用3根）。实际上，5根火柴能摆出的最大数是71。这里就体现了一个关键点：在位数固定的情况下，我们应该让高位的数字尽可能大。

基于这些分析，我们发现问题可以转化为：在总“成本”为n的前提下，从数字1-9（首位）和0-9（其他位）中选取数字进行组合，使得总成本等于n，且组合成的数字序列对应的整数值最大。这很像一个完全背包问题，但“最大数值”的比较规则（位数优先，同位数则字典序从高位比）引导我们走向贪心策略。

3. 核心算法策略：贪心思想的论证与实现

面对这个问题，动态规划（DP）是一种求所有可行解并比较的通用方法，但对于本题的规模（n可能达到100甚至更大）和输出要求（直接输出最大数），DP显得有点“杀鸡用牛刀”，而且实现起来状态转移和最终路径回溯构造数字比较繁琐。事实上，一个经过精心设计的贪心算法完全可以高效、正确地解决它。

3.1 为什么贪心是有效的？

贪心策略的核心思想是：从最高位到最低位，每一位都尽可能选择能放的最大数字，同时确保剩下的火柴棍能够至少摆出一个合法的数字序列（即至少能构成1位数）。

我们来论证一下这个贪心策略的正确性：

1. 位数优先原则：对于两个正整数，位数多的肯定比位数的大（除非有前导零，但已被禁止）。因此，我们首先要最大化位数。怎么最大化？就是让每一位消耗的火柴棍尽可能少。所以，我们应该用所需火柴棍最少的数字来“铺出”尽可能多的位数。观察映射表，数字1只需要2根火柴，是成本最低的（数字7需要3根，4需要4根，都比1多）。因此，最大可能的位数max_len = n / 2（如果n是偶数）或(n-1)/2（如果n是奇数，因为最少需要2根，奇数根会剩1根，需要和其他位组合消化掉）。
2. 高位优先原则：在位数固定的情况下，要使得整个数字最大，就必须让高位的数字尽可能大。因为只要高位数字更大，无论低位是什么，这个数都更大。例如，9xx一定大于8xx，无论后两位xx是什么。
3. 可行性保证：当我们决定在当前位置放一个数字d（消耗cost[d]根火柴）后，还剩下remain = n - cost[d]根火柴。我们必须确保这remain根火柴能够至少组成当前已确定位数-总位数这么多个数字，并且不能有前导零问题（对于剩下的位，第一位可以是0，因为此时它已经不是整个数字的最高位了）。最简单的可行性检查是：剩下的火柴数remain必须大于等于剩余位数 * 2（因为每位最少用2根火柴摆1）。

结合原则2和3，我们的贪心算法流程如下：

• 首先计算出最大可能的位数length = n / 2？ 不，更准确地说，我们需要动态判断。我们从第一位开始决策。
• 对于当前要决策的位（假设是第i位，从0开始计数），我们从大到小尝试数字d（从9到0，注意首位不能为0）。
• 对于每个尝试的数字d，计算消耗cost[d]，剩余火柴remain = n - cost[d]。
• 检查可行性：remain必须能够支持剩下的total_digits - i - 1位。即remain >= 2 * (total_digits - i - 1)。这里total_digits是我们期望的总位数，但我们在决策时其实还不知道最终位数，这是一个“鸡生蛋蛋生鸡”的问题。

3.2 破解“位数未知”的困境：逆向思维

上述流程卡在了“总位数未知”上。一个巧妙的解决方法是先确定位数，再逐位构造。

1. 确定位数：首先，我们求出在不考虑前导零、仅考虑最少消耗的情况下，用n根火柴能摆出的最大位数max_len。这很简单，全摆数字1即可，max_len = n / 2。但这样摆出来的数可能不是最大的，比如n=5，全摆1只能摆2个（11，用4根，还剩1根没法用），实际上最大是71（2位数）。所以，我们其实需要找到的是一个可行的位数，并且在这个位数下构造最大数。更稳健的方法是：我们枚举一个目标位数len，从可能的最大值开始向下尝试。对于每个len，我们检查是否能用n根火柴摆出一个len位数。检查的方法是：摆出len位全为1的数需要2*len根火柴。如果n >= 2*len，说明火柴足够摆出len位（因为可以用更耗火柴的数字替换1来消化多余的火柴）。同时，摆出len位全为8的数需要7*len根火柴，如果n <= 7*len，说明火柴不至于多到无法用完（因为可以用更省火柴的数字替换8来节省火柴）。所以，一个可行的len必须满足2*len <= n <= 7*len。
2. 构造数字：一旦我们找到了一个可行的位数len，我们就可以从最高位（第1位）到最低位（第len位）逐位确定数字。对于第i位（1 <= i <= len）：
   • 剩余需要摆的位数是len - i。
   • 剩余的火柴棍数量是remaining_sticks。
   • 我们从9到0遍历数字d（注意，如果是第一位i==1，则d从9到1，排除0）。
   • 对于每个d，消耗为cost[d]。选择d后，剩下的火柴为remaining_sticks - cost[d]。
   • 关键检查：剩下的火柴必须能够摆完剩下的位数。即必须满足：(remaining_sticks - cost[d]) >= 2 * (len - i)（下界：剩下每位数最少用2根）(remaining_sticks - cost[d]) <= 7 * (len - i)（上界：剩下每位数最多用7根）
   • 第一个满足上述条件的d，就是当前位能放的最大数字。选定它，更新remaining_sticks -= cost[d]，然后继续处理下一位。

这个算法是严谨的。我们从大到小枚举len，找到的第一个可行len，就是最大位数（因为位数越多数越大）。然后在这个位数约束下，用上述贪心法构造每一位，自然得到的就是该位数下的最大数，也就是全局最大数。

3.3 边界情况与特判

在实现之前，我们必须处理好边界：

• n < 2：连数字1都摆不出，直接输出-1。
• 不存在可行len：即对于所有可能的len（从1到n/2），都不满足2*len <= n <= 7*len。这种情况也可能发生，比如n=1。实际上，当n较小时需要仔细判断。我们可以写一个循环来寻找len。
• n很大时的效率：枚举len从n/2向下，最多尝试n/2次，每次构造需要遍历10个数字，检查剩余位数可行性是O(1)的。所以总复杂度是O(n)，对于n在几百上千的竞赛范围完全足够。

4. 代码实现与逐行解析

理论清晰后，我们来看C++实现。我会提供两个版本的代码：第一个是清晰版，严格遵循上述算法逻辑；第二个是优化紧凑版，更适合竞赛环境。

4.1 清晰版实现与注释

#include <iostream> #include <vector> using namespace std; int main() { // 每个数字所需的火柴棍数量，下标对应数字 int cost[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; int n; cin >> n; // 特判：如果火柴数连最小的数字1都摆不了 if (n < 2) { cout << -1 << endl; return 0; } // 步骤1：寻找最大可行位数 len int len = -1; // 位数最多不会超过 n/2 (全摆1)，我们从可能的最大位数开始向下找 for (int possible_len = n / 2; possible_len >= 1; --possible_len) { // 检查是否能用n根火柴摆出一个possible_len位数 // 最小消耗：全摆1 -> 2 * possible_len // 最大消耗：全摆8 -> 7 * possible_len if (n >= 2 * possible_len && n <= 7 * possible_len) { len = possible_len; break; // 找到第一个（即最大）可行位数就退出 } } // 如果没找到可行的位数 if (len == -1) { cout << -1 << endl; return 0; } // 步骤2：已知位数为len，开始逐位构造最大数字 int remaining_sticks = n; // 剩余火柴数 vector<int> digits; // 用来存储每一位的数字 for (int position = 1; position <= len; ++position) { // 当前是第position位（从1开始计数） // 剩余待确定的位数 int remaining_positions = len - position; // 从大到小尝试数字 // 如果是第一位，不能是0 int start_digit = (position == 1) ? 9 : 9; for (int d = start_digit; d >= 0; --d) { if (position == 1 && d == 0) { continue; // 首位跳过0 } int stick_cost = cost[d]; if (remaining_sticks < stick_cost) { continue; // 火柴不够摆这个数字 } int sticks_after_this = remaining_sticks - stick_cost; // 关键可行性检查： // 1. 剩下的火柴够不够摆完剩下的位（按最省的方式，每位数摆1，需2根） // 2. 剩下的火柴会不会太多，导致剩下的位即使全摆最耗火柴的8（7根）也用不完？ if (sticks_after_this >= 2 * remaining_positions && sticks_after_this <= 7 * remaining_positions) { // 这个数字d是可行的，并且是当前位能放的最大数字（因为我们从大到小枚举） digits.push_back(d); remaining_sticks = sticks_after_this; break; // 确定当前位，跳出数字枚举循环 } } // 理论上，内层循环一定会找到一个可行的d，因为len是预先验证过的。 } // 输出结果 for (int digit : digits) { cout << digit; } cout << endl; return 0; }

代码要点解析：

1. 可行性检查的深刻理解：if (sticks_after_this >= 2 * remaining_positions && sticks_after_this <= 7 * remaining_positions)这行代码是算法的灵魂。它确保了在选择了当前数字d后，剩余的火柴棍数量sticks_after_this必须在一个“可行区间”内。这个区间的下限2*remaining_positions意味着剩下的火柴至少够以最省的方式（全摆1）摆完剩下的位；上限7*remaining_positions意味着剩下的火柴即使以最奢侈的方式（全摆8）也能被完全消耗掉。只有同时满足这两个条件，才存在一种方案能用完所有火柴摆完剩下的位。
2. 首位处理：在数字枚举循环内，通过if (position == 1 && d == 0) continue;来跳过数字0，确保了最终数字没有前导零。
3. 循环终止：内层for循环在找到第一个可行的d后立即break，因为我们是从9到0降序枚举，第一个找到的可行数字就是当前位能放的最大数字。
4. 稳健性：算法先通过一个独立的循环找到可行的最大位数len，这个步骤和后续的构造步骤是解耦的，逻辑非常清晰，易于理解和调试。

4.2 竞赛优化版实现

清晰版便于理解，但在竞赛中，我们有时会追求更简洁的代码。下面的版本将“寻找位数”和“构造数字”合并到了一个更紧凑的循环中，其核心思想是：不预先确定精确的len，而是在构造过程中，确保剩下的火柴总能摆出至少1位数字（对于最后一位则是恰好用完）。

#include <iostream> using namespace std; int cost[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; int main() { int n; cin >> n; if (n < 2) { cout << -1 << endl; return 0; } // 核心贪心构造 int remaining = n; // 先确定第一位（不能为0） for (int d = 9; d >= 1; --d) { if (remaining >= cost[d] && (remaining - cost[d]) >= 2 * ((n / 2) - 1)) { // 这里 (n/2) 是最大可能位数的估计，用于粗略判断剩余火柴是否足够支撑后续位数。 // 一个更精确的判断是：计算摆完当前位后，剩余火柴是否能被后续位“消化”。 // 简化版：确保 remaining - cost[d] 是偶数且大于等于2。 // 但为了绝对正确，我们采用另一种更通用的方法： } } // 由于简化版容易有漏洞，这里更推荐使用清晰版的“先找位数”策略。 // 下面给出一个经过验证的、正确的紧凑版写法（动态规划思想结合贪心）： }

实际上，将“确定位数”和“逐位贪心”完全合并而不失正确性，需要更精巧的设计。一个可靠且简洁的竞赛写法如下，它利用了动态规划来预处理“摆出k位数所需的最少火柴数”，然后再贪心：

#include <iostream> #include <string> using namespace std; int cost[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; // min_cost[k] 表示摆出 k 位数所需要的最少火柴数（允许前导零） int min_cost[101]; // 假设n最大100，位数最多50 // max_cost[k] 表示摆出 k 位数所需要的最多火柴数（允许前导零） int max_cost[101]; int main() { int n; cin >> n; // 预处理最小和最大消耗 min_cost[0] = max_cost[0] = 0; for (int k = 1; k <= n/2; ++k) { min_cost[k] = min_cost[k-1] + 2; // 每多一位，最少加一个'1'(2根) max_cost[k] = max_cost[k-1] + 7; // 每多一位，最多加一个'8'(7根) } string ans = ""; int remaining = n; // 首先确定位数：找到最大的k，使得 min_cost[k] <= n <= max_cost[k] int max_len = 0; for (int k = n/2; k >= 1; --k) { if (min_cost[k] <= n && n <= max_cost[k]) { max_len = k; break; } } if (max_len == 0) { cout << -1 << endl; return 0; } // 现在我们知道要构造一个 max_len 位的数 for (int pos = 0; pos < max_len; ++pos) { int start_digit = (pos == 0) ? 9 : 9; // 首位从9开始，非首位也从9开始（因为0也在候选） for (int d = start_digit; d >= 0; --d) { if (pos == 0 && d == 0) continue; // 首位不能为0 if (remaining < cost[d]) continue; int sticks_after = remaining - cost[d]; int remaining_positions = max_len - pos - 1; // 检查剩余火柴能否被剩下的位数“容纳” if (sticks_after >= min_cost[remaining_positions] && sticks_after <= max_cost[remaining_positions]) { ans += char('0' + d); remaining = sticks_after; break; } } } cout << ans << endl; return 0; }

这个版本是清晰版的一个变体，它显式地预计算了min_cost和max_cost数组，使得后续的可行性检查sticks_after >= min_cost[...] && sticks_after <= max_cost[...]更加直观和高效。它同样正确且易于理解。

5. 测试用例与算法验证

任何算法代码都需要经过充分测试。我们设计几组有代表性的测试用例，涵盖正常情况、边界情况和易错情况。

我们可以用上面的清晰版或优化版代码运行这些测试用例，确保输出与预期一致。对于竞赛题，通常还会包含n较大的情况，比如n=100，我们的算法也应该能快速给出结果（一个长达50位的数字）。

一个重要的测试：验证贪心法的正确性为什么从高位开始，每次选最大的可行数字，能得到全局最优解？我们可以用反证法简要说明：假设在某一位（第i位）我们没有选择能放的最大数字d_max，而是选择了一个较小的数字d_small，那么后续位无论怎么摆，得到的数字在数值上都小于将第i位换成d_max、后续位做相应调整后得到的某个数字。因为只要高位更大，整个数就一定更大。而我们的可行性检查保证了选择d_max后，后续位存在一种方案能把火柴用完。因此，贪心选择是安全的。

6. 常见错误与避坑指南

在实现和调试这道题时，我见过同学们踩过不少坑。这里总结一下，帮你避开它们：

1. 混淆“最大数”与“最多位数”：这是最常见的错误。认为位数越多越好，所以优先用消耗最少的数字1来凑位数。但比如n=5时，凑3位需要至少6根火柴，不够。只能凑2位。在2位的情况下，应该追求高位数字最大，所以是71，而不是11（11只用4根，没用完）或17（高位1小于7）。策略应该是：在满足“恰好用完”的所有可能位数中，取位数最多的；在位数相同的情况下，用贪心使高位尽可能大。

2. 前导零处理不当：在逐位构造时，如果第一位尝试数字0成功，就会产生像0或0xxx这样的非法输出。必须在第一位枚举时跳过0。另外，在检查可行性时，对于非首位，数字0是允许的，它的成本是6，不要遗漏。

3. 可行性检查不完整：只检查了剩余火柴是否“足够”摆完剩下的位（sticks_after >= 2 * remaining_positions），而忘记了检查是否“过多”（sticks_after <= 7 * remaining_positions）。如果剩余火柴过多，即使后面每一位都摆最耗火柴的8（7根）也用不完，会导致最终火柴有剩余，违反“恰好用完”的条件。必须同时检查上下界。

4. 寻找可行位数时的逻辑错误：有人试图直接计算最大位数max_len = n / 2，然后就从这一位开始构造。但n/2只是最大可能位数，不一定可行。例如n=5，n/2=2，2位是可行的。但n=3时，n/2=1，1位可行（摆7或1，但1会剩1根，不符合“恰好用完”，所以只能摆7）。所以需要用一个循环去验证某个位数是否在[2*len, 7*len]区间内。

5. 对“无解”情况处理遗漏：只考虑了n<2的情况。实际上，对于某些n，可能没有任何长度的数字能满足“恰好用完”。例如n=1显然无解。n=2有解(1)。n=3有解(7)。n=11呢？最大位数5位（需10根），最小消耗10根，最大消耗35根，11在[10,35]内，有解。理论上，只要n>=2，似乎都有解？因为你可以全摆1，如果n是偶数，刚好用完；如果是奇数，你可以把其中一个1换成7（多消耗1根），或者做其他调整。实际上，可以证明对于n>=2，总是存在解的。但题目可能出于严谨要求输出-1，所以我们的代码保留无解判断逻辑是好的。

6. 使用字符串拼接的陷阱：在C++中，如果频繁使用ans = ans + char('0'+d)，会产生大量临时字符串，影响效率。更高效的做法是使用ans += char('0'+d)或ans.push_back(char('0'+d))。在竞赛中，这点性能差异通常可以忽略，但养成好习惯是有益的。

7. 变量初始化与更新：确保在每一位决策后，及时更新remaining_sticks。内层循环找到可行数字后要立刻break，避免后续数字覆盖。

把这些点都注意到，你的代码就能稳健地处理所有情况了。这道题很好的训练了我们对贪心算法适用条件的判断，以及对问题约束条件的细致分析能力。它告诉我们，即使是一个看起来简单的游戏，背后也可能隐藏着需要严谨推理的算法问题。