题解：P11229 [CSP-J 2024] 小木棍

· · 题解

前言

因为看到没有和我一样的做法，所以来写这篇题解了。

题目大意

给定一个整数 n ，输出能用刚好 n 根木棍拼成的没有前导 0 的最小整数。

题目分析

经过分析后我们发现 8 耗费的木棍数最多，所以答案一定为 ...8888888... ，所以我们只要确保前面几个数位拼出的数尽量小就可以了。

代码(有注释)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 5;
ll n, t, a[N] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int main(){
    cin >> t;
    while(t--){
        cin >> n;
        if(n == 1){//特判1
            cout << -1 << endl;
            continue;
        }
        if(n == 6){//特判6
            cout << 6 << endl;
            continue;
        }
        ll len = ceil(n / 7.0), sum = 0;//len是拆出来的数的长度,sum是当前耗费木棍数
        for(int i = 1; i < len; i++){
            for(int j = 0; j <= 9; j++){
                if(i == 1 && j == 0){//判前导0
                    continue;
                }
                if(sum + a[j] + (len - i) * 7 < n){//如果选j后后面全拆8也无法得到n，则跳过
                    continue;
                }
                sum += a[j];
                cout << j;
                break;
            }
        }
        for(int i = 0; i <= 9; i++){//防止n<7的情况出错
            if(sum + a[i] == n){
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}