CSP历年复赛题-P11229 [CSP-J 2024] 小木棍

原题链接：https://www.luogu.com.cn/problem/P11229

题意解读：求n根木棍拼出的最小数。

解题思路：

每个数字需要的木棍根数为：

数字   所需木棍根数
0 6
1 2
2 5
3 5
4 4
5 5
6 6
7 3
8 7
9 6
由于要拼出的数字尽可能小，那么所需相同根数的数字，越小越好，需要6根的有0和6，由于0不能在开头，因此都要保留，最终剩下可用的数字为：

数字 所需木棍根数
0 6
1 2
2 5
4 4
6 6
7 3
8 7
当然，优先用耗费木棍越多的数字越好，也就是优先用7根拼出8，作为数字的后缀，前缀就看剩下多少根木棍；

但是，并不一定先把所有的8都拼出来最好，还需要分情况讨论：

设m = n % 7， x = n / 7

1、如果m = 0，则拼出x个”8”是最好的；因为如果有一个不选”8”，以为要这7根要用于拼其他数字，至少变成了2位数，显然更大。

2、如果m = 1，如果x=0则无解输出”-1”；如果x>0则可以将8根拼出”10”再拼出x-1个”8”。

3、如果m = 2，用2根拼出”1”再拼出x个”8”；”1”用来开头是最小了。

4、如果m = 3，x=0时直接用3根拼出”7”；x=1时是10根可以拼出”78”也可以拼出”22”，显然”22”更好；x>1时可以用17根拼出”200”或者”788”或者”228”，显然”200”最好，再拼出x-2个”8”。没有必要再考虑24根的情况，因为24根至少也要拼成4个数字，开头”200”已是最佳。

5、如果m = 4，x=0时时直接用4根拼出”4”；x>0时先用11根拼出”20”优于”48”，再拼出x-1个”8”。

6、如果m = 5，先用5根拼出2，再拼出x个”8”。

7、如果m = 6，先用6根拼出6，再拼出x个”8”。

100分代码：

#include <bits/stdc++.h>
using namespace std;

void print8(string pre, int x)
{
    cout << pre;
    for(int i = 1; i <= x; i++) cout << 8;
    cout << endl;
}

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        cin >> n;
        int m = n % 7, x = n / 7;
        if(m == 0) print8("", x);
        else if(m == 1)
        {
            if(x == 0) cout << -1 << endl;
            else print8("10", x - 1);
        }
        else if(m == 2) print8("1", x);
        else if(m == 3) 
        {
            if(x == 0) cout << 7 << endl;
            else if(x == 1) print8("22", x - 1);
            else print8("200", x - 2);
        }
        else if(m == 4) 
        {
            if(x == 0) cout << 4 << endl;
            else print8("20", x - 1);
        }
        else if(m == 5) print8("2", x);
        else if(m == 6) print8("6", x);
    }
    return 0;
}