P11229 [CSP-J 2024] 小木棍（官方数据）题解

aaa_lvzekai · 2024-11-16 15:44:37 · 个人记录

题目介绍

用小木棍摆 0 \sim 9，组成一个正整数，满足如下条件：

• 拼出这个数恰好使用 n 根小木棍；
• 拼出的数没有前导 0；
• 在满足以上两个条件的前提下，这个数尽可能小。

如果无解，输出 -1。

原题链接

100pts 思路讲解

算法：贪心（找规律）

时间复杂度：O(n)

首先发现数字 8 使用的小木棍数最多，想让最后的数最小，首先位数要最少，要位数最少所以要多选 8，剩下多余的小木棍用来做小数字。

注：在木棍少的时候取 8 不划算，记得特判。

代码+注释

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        if(n==1)
        {
            cout<<"-1\n";
        }
        else if(n==2)
        {
            cout<<"1\n";
        }
        else if(n==3)
        {
            cout<<"7\n";
        }
        else if(n==4)
        {
            cout<<"4\n";
        }
        else if(n==5)
        {
            cout<<"2\n";
        }
        else if(n==6)
        {
            cout<<"6\n";
        }
        else if(n==7)
        {
            cout<<"8\n";
        }
        else if(n==10)
        {
            cout<<"22\n";
        }
        else if(n%7==0)
        {
            for(int i=1;i<=n/7;i++)
            {
                cout<<"8";
            }
            cout<<"\n";
        }
        else if(n%7==1)
        {
            cout<<"10";
            for(int i=1;i<=(n-8)/7;i++)
            {
                cout<<"8";
            }
            cout<<"\n";
        }
        else if(n%7==2)
        {
            cout<<"1";
            for(int i=1;i<=(n-2)/7;i++)
            {
                cout<<"8";
            }
            cout<<"\n";
        }
        else if(n%7==3)
        {
            cout<<"200";
            for(int i=1;i<=(n-17)/7;i++)
            {
                cout<<"8";
            }
            cout<<"\n";
        }
        else if(n%7==4)
        {
            cout<<"20";
            for(int i=1;i<=(n-11)/7;i++)
            {
                cout<<"8";
            }
            cout<<"\n";
        }
        else if(n%7==5)
        {
            cout<<"2";
            for(int i=1;i<=(n-5)/7;i++)
            {
                cout<<"8";
            }
            cout<<"\n";
        }
        else if(n%7==6)
        {
            cout<<"6";
            for(int i=1;i<=(n-6)/7;i++)
            {
                cout<<"8";
            }
            cout<<"\n";
        }
    }
    return 0;
}

100pts 记录