P11229 题解

dongrunxuan · 2024-11-03 20:27:34 · 题解

前言

此题差点让我无法拿下普及组前三题。好在最后调出来了。谨以此题解记念我最后一次 CSP-J。

题意简述

给你 n 根木棍，摆出一个最小的数。

做法

本题分两个细节思考。首先是贪心，显然，由于数字 8 消耗的木棍最多，所以优先选择不断在后面补 8，这样摆的数字位数一定最小。

看到题解区大部分人都是使用余数进行分类讨论，其实大可不必。考场上我没想那么多，直接不断添 8 并减小 n，当 n 被降到小数据规模时，可以采取暴力方法计算出小规模 n 所能构成的最小数字，然后在 8 前面添上枚举出的前几位。这种方法的正确性显而易见。

代码

放上赛后重构代码，码风丑，不喜勿喷。

#include<bits/stdc++.h>
using namespace std;
int T;
int n,ans;
int val[15]={6,2,5,5,4,5,6,3,7,6};
bool check(int x)
{
    int res=0;
    while(x)
    {
        res+=val[x%10];
        x/=10;
    }
    return res==n;
}
int main()
{
    //freopen("T3.in","r",stdin);
    //freopen("zj.out","w",stdout);
    cin>>T;
    while(T--)
    {
        ans=0;
        cin>>n;
        if(n==1)
        {
            cout<<-1<<'\n';
            continue;
        }
        while(n>25)
        {
            n-=7;
            ans++;
        }   
        for(int i=1;i<=1e6;i++)
        {
            if(check(i))
            {
                cout<<i;
                break;
            }
        }
        for(int i=1;i<=ans;i++)
        {
            cout<<8;
        }
        cout<<endl;
    }
    return 0;
}