题解

Atcoder Beginner Contest 257 problem E 题解

题目链接:______

题目大意

高桥有一个整数$x$。最初，$x$=0。高桥可以多次执行以下操作：

• 选择整数$i（1≤i≤9)$. 支付$Ci$日元（日本的货币）以将$x$替换为$10x+i$。

高桥的预算是$N$日元。在不超过预算的情况下，找出最终x的最大可能值。

数据范围

• $1\leq n \leq 10^6$
• $1\leq Ci \leq N$
• 输入全部为整数

样例输入1

5
5 4 3 3 2 5 3 5 3

样例输出1

95

样例解释1

按照$i=9$的顺序进行操作，再按照$i=5$的顺序进行操作，$x$会发生以下变化。
$0→9→95$
支付的总金额为$C9+C5=3+2=5$日元，不超过预算。答案是95，因为它可以证明通过不超出预算的操作方法不可能做出96或更大的整数。

样例输入2

20
1 1 1 1 1 1 1 1 1

样例输出2

99999999999999999999

解析

本题使用贪心算法解题。
假设此人共支付$k$次，通过观察可知，其实际上所得的数必然是一个$k$位数。因此，此题可转化为：使用$N$日元，组成一个$k$位数，使得总花销不超过$N$的情况下，组成的数最大。
通常情况下，数的位数越多，则数越大，即$k$越大，则$x$更大。所以，无论是否花完预算，组成的数都必然会存在最大的位数，最优解的位数必然等于最大的位数，其必然等于：

$[\frac {N}{C_{min}}]$

因此，我们可先求出该数最多的位数，再用贪心算法从大到小枚举每一位，从而求出最优解。

代码实现

以上算法代码实现如下：

#include<bits/stdc++.h>
using namespace std;
#define N 1000000
using ll=long long;
int n,c[10],ans[N],min_c=0x3f3f3f3f;
int main(){
    std::ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=9;i++) cin>>c[i],min_c=min(min_c,c[i]);
    int cnt=n/min_c,n_=n;
    for(int i=1;i<=cnt;i++){
        for(int j=9;j>=1;j--){
            if(c[j]+(cnt-i)*min_c<=n_){
                ans[i]=j,n_-=c[j];
                break;
            }
        }
    }
    for(int i=1;i<=cnt;i++) cout<<ans[i];
    return 0;
}