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

Starmoon_dhw · 2024-10-26 19:13:32 · 题解

Solution

提供一种贪心的思路。

由于构造的数要求最小，所以我们要保证构造的数的位数最少，也要保证越前面的数越小，所以我们可以在可以取的情况下尽可能的取小的数。

所以我们可以一位位的填，每一位最多只有 7 种可能，因为用相同的木棍，我们肯定拼接小的数字，所以我们可以把这些数字以及所需的木棍数用结构体储存，如下：

a[1].mugun=2;
a[1].num=1;
a[2].mugun=3;
a[2].num=7;
a[3].mugun=4;
a[3].num=4;
a[4].mugun=5;
a[4].num=2;
a[5].mugun=6;
a[5].num=0;
a[6].mugun=6;
a[6].num=6;
a[7].mugun=7;
a[7].num=8;

注意由于 0 不能做第一位数字，所以我们有需要把 6 也存起来，然后最好按照数字大小排序，当然也可以在赋值的时候做好这件事情、

接下来我们需要求出构造出的数字的位数，很好求为：(n-1)/7+1 ，因为只有在位数最小的的前提下才可以让构造数的前面的数字最小。

注意，由于 1 无法处理所以我们需要特判，并且因为 0 不能开头所以需要一个 flag 来判断是否可以使用 0。

Code

#include<bits/stdc++.h>
using namespace std;
int T,n;
struct node{
    int mugun,num;
}a[15];
bool cmp(node a,node b)
{
    return a.num<b.num;
}
signed main()
{
    a[1].mugun=2;
    a[1].num=1;
    a[2].mugun=3;
    a[2].num=7;
    a[3].mugun=4;
    a[3].num=4;
    a[4].mugun=5;
    a[4].num=2;
    a[5].mugun=6;
    a[5].num=0;
    a[6].mugun=6;
    a[6].num=6;
    a[7].mugun=7;
    a[7].num=8;
    sort(a+1,a+1+7,cmp);
    cin>>T;
    while(T--)
    {
        cin>>n;

        if(n==1)
        {
            cout<<"-1\n";
            continue;
        }
        int ws=(n-1)/7+1;
        int flag=1;
        while(ws>0)
        {
            for(int i=1;i<=7;i++)
            {
                if((ws-1)*7>=n-a[i].mugun&&n>=a[i].mugun)
                {
                    if(a[i].num==0&&flag)
                        continue;
                    ws--;
                    cout<<a[i].num;
                    flag=0;
                    n-=a[i].mugun;
                    break;
                }
            }
        }
        cout<<"\n";

     } 
    return 0;
}