AT_abc257_e 题解

ikunTLE · 2024-12-22 23:43:35 · 题解

题目传送门

思路

为了使 x 最大，必须使 x 的位数最大。在保证位数的情况下，必须要先使高位最大，再使更低的位数更大。也就是说，最终答案从高位到低位一定是个不升的序列。

首先需要求出序列的长度 L，则 L=\lfloor\frac{N}{\min\{C_i\}}\rfloor。我们保证 L 最长的前提下，枚举 1 到 L。每一位一定是越大越好，故从大向小枚举，如果可以直接输出当前数字，更新当前 N 的值，然后接着枚举下一位。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
int a[15];
int main(){
    int n=read(),minn=INT_MAX;
    for(int i=1;i<=9;++i){
        a[i]=read();
        minn=min(minn,a[i]);
    }
    int l=n/minn;
    for(int i=1;i<=l;++i)
        for(int j=9;j>=1;--j)
            if(n-a[j]>=(l-i)*minn){
                printf("%d",j);
                n-=a[j];
                break;
            }
    printf("\n");
    return 0;
}