CSP 真题解析：[CSP-J 2024-T3] 小木棍-平芜编程栈

[CSP-J 2024-T3] 小木棍

摘要：本题是 CSP-J 2024 第三题，要求用恰好n nn根长度相等的小木棍拼出一个无前导零的正整数，并使该数尽可能小。题解采用贪心 + 模 7 分类讨论：优先用木棍数最多的数字8（7 根）以减少位数，再根据n m o d 7 n \bmod 7nmod7的余数调整最高位数字，最终在位数最少的前提下使高位最小。需注意n = 6 n=6n=6时不能输出0、n ≥ 17 n \geq 17n≥17且余数为 3 时应输出200...等易错细节。

输入输出样例 #1

输入 #1

5 1 2 3 6 18

输出 #1

-1 1 7 6 208

说明/提示

【样例 1 解释】

对于第一组测试数据，不存在任何一个正整数可以使用恰好一根小木棍摆出，故输出− 1 -1−1。
对于第四组测试数据，注意0 00并不是一个满足要求的方案。摆出9 99、41 4141以及111 111111都恰好需要6 66根小木棍，但它们不是摆出的数最小的方案。
对于第五组测试数据，摆出208 208208需要5 + 6 + 7 = 18 5 + 6 + 7 = 185+6+7=18根小木棍。可以证明摆出任何一个小于208 208208的正整数需要的小木棍数都不是18 1818。注意尽管拼出006 006006也需要18 1818根小木棍，但因为这个数有前导零，因此并不是一个满足要求的方案。

【数据范围】

对于所有测试数据，保证：1 ≤ T ≤ 50 1 \leq T \leq 501≤T≤50，1 ≤ n ≤ 10 5 1 \leq n \leq 10^51≤n≤105。

测试点编号	n ≤ n\leqn≤	特殊性质
1 11	20 2020	无
2 22	50 5050	^
3 33	10 3 10^3103	A
4 , 5 4,54,5	10 5 10^5105	^
6 66	10 3 10^3103	B
7 , 8 7,87,8	10 5 10^5105	^
9 99	10 3 10^3103	无
10 1010	10 5 10^5105	^

特殊性质 A：保证n nn是7 77的倍数且n ≥ 100 n \geq 100n≥100。

特殊性质 B：保证存在整数k kk使得n = 7 k + 1 n = 7k + 1n=7k+1，且n ≥ 100 n \geq 100n≥100。

思路要点

我们手里有n nn根木棍，要拼出一个正整数（不能有前导0 00），要求恰好用完n nn根木棍，并且让这个正整数尽可能小。

首先，我们要明确每个数字需要消耗的木棍数量：

数字1需要 2 根
数字7需要 3 根
数字4需要 4 根
数字2,3,5需要 5 根
数字0,6,9需要 6 根
数字8需要 7 根

撇开题目中“小木棍拼数字”的背景外壳，这道题的本质是：贪心算法（Greedy） + 整数模运算与分类讨论。在给定的数字总和（木棍数）限制下，组合出位数最少、且高位数字最小的数。

关键思路

如何让拼出来的数字“尽可能小”？这里有两个核心的贪心策略：

位数越少，数值越小：比如任意一个 2 位数都一定小于 3 位数。因此，我们要让每个数字消耗尽量多的木棍。观察发现，数字8消耗的木棍最多（7根）。所以，我们应该尽可能多地使用数字8。
高位的数字越小，数值越小：如果位数相同，决定大小的关键在最高位。例如18小于81。因此，我们要把消耗木棍少、数值小的数字尽量往前排。

基于以上两点，我们可以用n nn除以 7：

商k = n / 7 k = n / 7k=n/7表示我们最多能拼出多少个数字8。
余数r = n ( m o d 7 ) r = n \pmod 7r=n(mod7)则是剩下的木棍，我们需要用这些余数和前面的8进行微调，凑出最小的开头数字。

解题步骤

我们以样例输入中的n = 18 n = 18n=18为例，模拟代码的执行过程：

变量定义与初始化：
定义全局变量int T, n;用于存储测试组数和当前木棍数。
定义辅助函数void prt(int k)，用于连续输出k kk个数字8。
读入数据：

系统读入T = 5 T = 5T=5，表示有 5 组数据。

进入while(T--)循环，读入当前组的木棍数n = 18 n = 18n=18。

条件分支判断：
首先判断n < 2，不成立（最少摆出数字 1 需要 2 根木棍）。
再判断n < 8，不成立（18 ≥ 8 18 \ge 818≥8）。程序进入else分支，开始核心的模 7 分类讨论。
公式计算与输出：k = 18 / 7 = 2 k = 18 / 7 = 2k=18/7=2，r = 18 ( m o d 7 ) = 4 r = 18 \pmod 7 = 4r=18(mod7)=4

程序进入switch(r)，匹配到case 4：据贪心原则，余下 4 根木棍加上一个8（7 根）共 11 根木棍。能拼出的最小两位数是20（2用 5 根，0用 6 根，5 + 6 = 11 5 + 6 = 115+6=11）。

执行printf("20");。执行prt(--k);：此时k自减 1 变成 1，调用函数打印 1 个8。

最终输出结果：208。

本题易错点

坑一：前导零与数字0的限制
要点提醒：当n = 6 n = 6n=6时，虽然数字0只需要 6 根木棍且比6小，但题目要求拼出正整数，因此单个0是非法的，必须输出6。但在大数字中间（如n = 18 n = 18n=18输出208），0可以作为中间位或低位存在。
坑二：r = 3 r = 3r=3时的隐藏陷阱
要点提醒：当n = 10 n = 10n=10时，k = 1 , r = 3 k = 1, r = 3k=1,r=3，答案是22 2222，但是当n = 17 n = 17n=17时，k = 2 , r = 3 k = 2, r = 3k=2,r=3，如果按之前思路尽可能末尾都是8 88（把17 1717看成10 + 7 10 + 710+7），那剩下10 1010根木棍拼出的前缀最小的数是22 2222，答案是228 228228。但如果末尾不是8 88，把17 1717看成11 + 6 11 + 611+6，可以得到更小的200 200200，也就是 $n > 17 $且r = 3 r = 3r=3的情况都应前缀数字200 200200才是最小。
坑三：纯暴力搜索（DFS）
要点提醒：试图从 1 开始枚举所有正整数去校验木棍数。当n = 10 5 n = 10^5n=105时，答案是一个长达一万多位的数字，暴力搜索连第一组数据都跑不完。

参考代码

#include<bits/stdc++.h>usingnamespacestd;intT,n;// T: 测试数据组数, n: 每组的木棍数量// 工具函数：连续打印 k 个数字 8voidprt(intk){for(inti=1;i<=k;i++){printf("8");}}intmain(){scanf("%d",&T);while(T--){scanf("%d",&n);// 特殊情况 1：少于 2 根木棍，无法拼出任何正整数if(n<2){printf("-1");}// 特殊情况 2：个位数木棍，直接特判输出最优解elseif(n<8){switch(n){case2:printf("1");break;case3:printf("7");break;case4:printf("4");break;case5:printf("2");break;case6:printf("6");break;// 注意：不能是 0，因为要求正整数case7:printf("8");break;}}// 通用情况：n >= 8，采用模 7 贪心策略else{intk=n/7;// 最多可以拼出的 8 的个数intr=n%7;// 模 7 的余数switch(r){case0:// 恰好整除，全部填 8prt(k);break;case1:// 余 1 根：向 8 借 1 根凑成 8 根，拼出 "10"printf("10");prt(--k);break;case2:// 余 2 根：直接在最前面放 "1" (2根)，剩下填 8printf("18");prt(--k);break;case3:// 余 3 根：分情况讨论if(n<17){// 也就是 n = 10 的特殊情况printf("22");}else{// n >= 17 时，借两个 8 凑成 17 根，拼出 "200"printf("200");prt(k-2);}break;case4:// 余 4 根：借一个 8 凑成 11 根，拼出 "20"printf("20");prt(--k);break;case5:// 余 5 根：借一个 8 凑成 12 根，拼出 "28"printf("28");prt(--k);break;case6:// 余 6 根：借一个 8 凑成 13 根，拼出 "68"printf("68");prt(--k);break;}}printf("\n");// 每组数据输出完毕后换行}return0;}