火柴数字问题解析：贪心算法在C++竞赛中的实战应用-北京尧图网络

1. 问题引入从火柴棍到数字编码不知道大家有没有玩过用火柴棍摆数字的游戏几根小小的火柴通过不同的排列组合就能表示出0到9这十个数字。这看似是一个简单的趣味游戏但在算法竞赛中它却能衍生出非常考验思维和编程能力的问题。上海计算机学会2021年5月月赛C乙组的T1题“火柴数字一”正是这样一个将生活趣味与严谨算法结合的典型例子。这道题的核心是给定一个整数n以及每个数字0-9所需要的火柴棍数量题目会给出一个固定的映射关系比如常见的“标准火柴数字”我们需要计算出恰好使用n根火柴棍能够摆出的最大整数是多少。这里有几个关键约束摆出的数字不能有前导零我们必须用完所有的n根火柴一根不多一根不少我们追求的是数值上的最大而不是位数最多。乍一看这有点像我们小时候玩的“用给定钱币凑出最大金额”的问题但加入了“每个数字成本火柴数不同”和“禁止前导零”的复杂条件。它不仅仅考察基本的循环和条件判断更深入地触及了贪心算法和动态规划的思维边界。很多同学的第一反应可能是用贪心从最高位开始尽可能放能摆出的最大数字。这个思路方向是对的但在“恰好用完”和“处理零”这两个点上极其容易踩坑。我见过不少实现跑样例似乎没问题但一提交就Wrong Answer问题往往就出在细节处理上。接下来我将彻底拆解这个问题。我们会先明确题目给出的“数字-火柴棍”映射规则这是所有计算的基础。然后我会带你一步步分析贪心策略为什么是可行的以及如何严谨地处理那些恼人的边界情况。最后我们会给出清晰、健壮且高效的C实现代码并附上详细的注释和测试用例。无论你是正在备战信奥赛的选手还是对算法设计感兴趣的开发者相信这篇深入的分析都能让你有所收获。2. 问题建模与规则定义在动手写代码之前我们必须把问题从自然语言描述转化为精确的数学模型。这是解决任何算法问题的第一步也是最关键的一步理解偏差会导致全盘皆输。首先题目会给出0到9每个数字所需要的火柴棍数量。这里我们采用最常见的一种“标准火柴数字”摆法也是许多类似题目包括国际赛题的默认设定其映射关系如下数字所需火柴棍数量06122535445566738796我们可以用一个数组来存储这个映射关系例如int cost[10] {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};。其中cost[i]表示摆出数字i需要的火柴数。接下来我们定义问题的输入和输出输入一个正整数n代表总共可用的火柴棍数量。输出一个正整数表示恰好使用n根火柴棍能摆出的最大整数。如果无法用n根火柴棍摆出任何一个符合要求的整数例如n 2因为最小的数字1也需要2根火柴则输出-1。约束条件分析恰好用完使用的火柴总数必须严格等于n。不能多也不能少。这直接排除了“小于等于n”这种更简单的背包问题变种。无前导零摆出的数字最高位不能是0。例如n6时可以摆出数字0需要6根但这是无效的因为0不是一个正整数通常题目要求输出正整数。更重要的是对于多位数比如n12你不能摆出06这样的数即使它数值上等于6。你必须确保第一位是1-9中的某个数字。最大化数值在满足上述条件的所有方案中我们需要找到数值最大的那个。注意数值最大并不直接等同于位数最多。例如用5根火柴可以摆出71325根数值71也可以摆出1但只用2根不符合“恰好用完”或者摆出7只用3根。实际上5根火柴能摆出的最大数是71。这里就体现了一个关键点在位数固定的情况下我们应该让高位的数字尽可能大。基于这些分析我们发现问题可以转化为在总“成本”为n的前提下从数字1-9首位和0-9其他位中选取数字进行组合使得总成本等于n且组合成的数字序列对应的整数值最大。这很像一个完全背包问题但“最大数值”的比较规则位数优先同位数则字典序从高位比引导我们走向贪心策略。3. 核心算法策略贪心思想的论证与实现面对这个问题动态规划DP是一种求所有可行解并比较的通用方法但对于本题的规模n可能达到100甚至更大和输出要求直接输出最大数DP显得有点“杀鸡用牛刀”而且实现起来状态转移和最终路径回溯构造数字比较繁琐。事实上一个经过精心设计的贪心算法完全可以高效、正确地解决它。3.1 为什么贪心是有效的贪心策略的核心思想是从最高位到最低位每一位都尽可能选择能放的最大数字同时确保剩下的火柴棍能够至少摆出一个合法的数字序列即至少能构成1位数。我们来论证一下这个贪心策略的正确性位数优先原则对于两个正整数位数多的肯定比位数的大除非有前导零但已被禁止。因此我们首先要最大化位数。怎么最大化就是让每一位消耗的火柴棍尽可能少。所以我们应该用所需火柴棍最少的数字来“铺出”尽可能多的位数。观察映射表数字1只需要2根火柴是成本最低的数字7需要3根4需要4根都比1多。因此最大可能的位数max_len n / 2如果n是偶数或(n-1)/2如果n是奇数因为最少需要2根奇数根会剩1根需要和其他位组合消化掉。高位优先原则在位数固定的情况下要使得整个数字最大就必须让高位的数字尽可能大。因为只要高位数字更大无论低位是什么这个数都更大。例如9xx一定大于8xx无论后两位xx是什么。可行性保证当我们决定在当前位置放一个数字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 破解“位数未知”的困境逆向思维上述流程卡在了“总位数未知”上。一个巧妙的解决方法是先确定位数再逐位构造。确定位数首先我们求出在不考虑前导零、仅考虑最少消耗的情况下用n根火柴能摆出的最大位数max_len。这很简单全摆数字1即可max_len n / 2。但这样摆出来的数可能不是最大的比如n5全摆1只能摆2个11用4根还剩1根没法用实际上最大是712位数。所以我们其实需要找到的是一个可行的位数并且在这个位数下构造最大数。更稳健的方法是我们枚举一个目标位数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。构造数字一旦我们找到了一个可行的位数len我们就可以从最高位第1位到最低位第len位逐位确定数字。对于第i位1 i len剩余需要摆的位数是len - i。剩余的火柴棍数量是remaining_sticks。我们从9到0遍历数字d注意如果是第一位i1则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。这种情况也可能发生比如n1。实际上当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; // 剩余火柴数 vectorint 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. 剩下的火柴会不会太多导致剩下的位即使全摆最耗火柴的87根也用不完 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; }代码要点解析可行性检查的深刻理解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也能被完全消耗掉。只有同时满足这两个条件才存在一种方案能用完所有火柴摆完剩下的位。首位处理在数字枚举循环内通过if (position 1 d 0) continue;来跳过数字0确保了最终数字没有前导零。循环终止内层for循环在找到第一个可行的d后立即break因为我们是从9到0降序枚举第一个找到的可行数字就是当前位能放的最大数字。稳健性算法先通过一个独立的循环找到可行的最大位数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预期输出说明21只能摆一个数字12根。37可以摆73根比12根剩1根无效大。411可以摆两个1224根数值11。注意4需要4根但11比4大。571摆7(3根)和1(2根)共5根数值71。这是经典用例容易错成17或5。6111摆三个12*36根数值111。也可以摆0或6但它们是1位数小于111。7711摆7(3根)和两个1(2*24根)共7根数值711。注意不是171或117。1011111五个1用10根。11711117(3根) 四个1(8根) 11根。157111117(3根) 五个1(10根) 13根不对15根应该能摆更多位。让我们算一下全摆1可摆7位14根剩1根。我们需要用掉15根。最大位数是7位因为2714157749。用贪心法第一位尝试96根剩9根需摆6位最少需12根不够。尝试87根剩8根需摆6位最少需12根不够。尝试73根剩12根需摆6位最少需12根满足。所以第一位是7。剩余12根摆6位全摆1刚好12根。所以结果是71111117111111等等7位应该是76个1是7111111。验证32*615正确。所以输出是7111111。1-1无法摆出任何数字。0-1无法摆出任何数字。我们可以用上面的清晰版或优化版代码运行这些测试用例确保输出与预期一致。对于竞赛题通常还会包含n较大的情况比如n100我们的算法也应该能快速给出结果一个长达50位的数字。一个重要的测试验证贪心法的正确性为什么从高位开始每次选最大的可行数字能得到全局最优解我们可以用反证法简要说明假设在某一位第i位我们没有选择能放的最大数字d_max而是选择了一个较小的数字d_small那么后续位无论怎么摆得到的数字在数值上都小于将第i位换成d_max、后续位做相应调整后得到的某个数字。因为只要高位更大整个数就一定更大。而我们的可行性检查保证了选择d_max后后续位存在一种方案能把火柴用完。因此贪心选择是安全的。6. 常见错误与避坑指南在实现和调试这道题时我见过同学们踩过不少坑。这里总结一下帮你避开它们混淆“最大数”与“最多位数”这是最常见的错误。认为位数越多越好所以优先用消耗最少的数字1来凑位数。但比如n5时凑3位需要至少6根火柴不够。只能凑2位。在2位的情况下应该追求高位数字最大所以是71而不是1111只用4根没用完或17高位1小于7。策略应该是在满足“恰好用完”的所有可能位数中取位数最多的在位数相同的情况下用贪心使高位尽可能大。前导零处理不当在逐位构造时如果第一位尝试数字0成功就会产生像0或0xxx这样的非法输出。必须在第一位枚举时跳过0。另外在检查可行性时对于非首位数字0是允许的它的成本是6不要遗漏。可行性检查不完整只检查了剩余火柴是否“足够”摆完剩下的位sticks_after 2 * remaining_positions而忘记了检查是否“过多”sticks_after 7 * remaining_positions。如果剩余火柴过多即使后面每一位都摆最耗火柴的87根也用不完会导致最终火柴有剩余违反“恰好用完”的条件。必须同时检查上下界。寻找可行位数时的逻辑错误有人试图直接计算最大位数max_len n / 2然后就从这一位开始构造。但n/2只是最大可能位数不一定可行。例如n5n/222位是可行的。但n3时n/211位可行摆7或1但1会剩1根不符合“恰好用完”所以只能摆7。所以需要用一个循环去验证某个位数是否在[2*len, 7*len]区间内。对“无解”情况处理遗漏只考虑了n2的情况。实际上对于某些n可能没有任何长度的数字能满足“恰好用完”。例如n1显然无解。n2有解(1)。n3有解(7)。n11呢最大位数5位需10根最小消耗10根最大消耗35根11在[10,35]内有解。理论上只要n2似乎都有解因为你可以全摆1如果n是偶数刚好用完如果是奇数你可以把其中一个1换成7多消耗1根或者做其他调整。实际上可以证明对于n2总是存在解的。但题目可能出于严谨要求输出-1所以我们的代码保留无解判断逻辑是好的。使用字符串拼接的陷阱在C中如果频繁使用ans ans char(0d)会产生大量临时字符串影响效率。更高效的做法是使用ans char(0d)或ans.push_back(char(0d))。在竞赛中这点性能差异通常可以忽略但养成好习惯是有益的。变量初始化与更新确保在每一位决策后及时更新remaining_sticks。内层循环找到可行数字后要立刻break避免后续数字覆盖。把这些点都注意到你的代码就能稳健地处理所有情况了。这道题很好的训练了我们对贪心算法适用条件的判断以及对问题约束条件的细致分析能力。它告诉我们即使是一个看起来简单的游戏背后也可能隐藏着需要严谨推理的算法问题。

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

相关推荐

网盘限速怎么破？从测速方法论到不限速网盘实测

微型封装PECL/LVDS差分振荡器：高速时钟设计的选型与实战

从零入门机器人：机械臂仿真与具身智能学习路线

更多资讯

烟台无忧低压电工证全国通用怎么操作？证书过期了不知道怎么复审延期？

电工证二级学习资料内部消息：实操考试心里没底怕挂科？别慌，这几点帮你稳过

3个实操考试翻车现场教你避开水电工证考证要求千万别踩坑

南平哪里考低压电工证含金量决定你能否顺利上岗

莱州在哪复审电工证保姆级教程：工地太忙根本没时间复习考试怎么办

质检需不需要电工证网上查询后真相大白，工地太忙根本没时间复习考试

今日更新

普宁电工证在哪报名官方回应怕考不过白交培训费？这些避坑干货你必须知道

高压电工证登高练习题在哪考合格率高？怕考不过白交培训费

电工作业登记表通过率揭秘：怕考不过白交培训费？洛阳学员亲测经验全公开

本周精选

普宁电工证在哪报名官方回应怕考不过白交培训费？这些避坑干货你必须知道

高压电工证登高练习题在哪考合格率高？怕考不过白交培训费

电工作业登记表通过率揭秘：怕考不过白交培训费？洛阳学员亲测经验全公开

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？

相关推荐

网盘限速怎么破？从测速方法论到不限速网盘实测

微型封装PECL/LVDS差分振荡器：高速时钟设计的选型与实战

从零入门机器人：机械臂仿真与具身智能学习路线

更多资讯

烟台无忧低压电工证全国通用怎么操作？证书过期了不知道怎么复审延期？

电工证二级学习资料内部消息：实操考试心里没底怕挂科？别慌，这几点帮你稳过

3个实操考试翻车现场教你避开水电工证考证要求千万别踩坑

南平哪里考低压电工证 含金量决定你能否顺利上岗

莱州在哪复审电工证保姆级教程：工地太忙根本没时间复习考试怎么办

质检需不需要电工证网上查询后真相大白，工地太忙根本没时间复习考试

今日更新

普宁电工证在哪报名官方回应怕考不过白交培训费？这些避坑干货你必须知道

高压电工证登高练习题在哪考合格率高？怕考不过白交培训费

电工作业登记表通过率揭秘：怕考不过白交培训费？洛阳学员亲测经验全公开

本周精选

普宁电工证在哪报名官方回应怕考不过白交培训费？这些避坑干货你必须知道

高压电工证登高练习题在哪考合格率高？怕考不过白交培训费

电工作业登记表通过率揭秘：怕考不过白交培训费？洛阳学员亲测经验全公开

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？

南平哪里考低压电工证含金量决定你能否顺利上岗