Atcoder 题解

Atcoder Beginner Contest 257 problem E 题解

题目链接:点我

题目大意

一个人有$N$元钱，他的面前有9个数字，每个数字对应的价格为$C_i$。这个人有一个数$X$，开始时$X$为$0$。如果这个人购买了第$i$个数字，那么他的$N$对应的减去$C_i$，他的$X$对应的会变为$X*10+i$。(一个数可以被购买无数次。)

求如何分配他的N元钱，是的他获得的$X$值最大。输出这个最大值。

样例输入1

5
5 4 3 3 2 5 3 5 3

样例输出1

95

样例解释1

可以购买第$9$个和第$5$个数字。这样花费是$5$，得到的数是$95$。
可以证明，找不到更大的方案可以使答案大于$95$。

样例输入2

20
1 1 1 1 1 1 1 1 1

样例输出2

99999999999999999999

样例解释2

可以购买$20$次第$9$个数。这样会得到一个最大的$20$位数。
注意:答案可能不适用于64位整型数。

数据范围

• $1 \leq N \leq 10^6$
• $1 \leq C_i \leq N$
• 所有的输入均为整型数。

解析

这道题是一道妥妥的贪心。

要使得所得的数最大，那么首先决定性的因素便是这个数的位数。所以，我们可以找到数组$C$中的最小值$C_{min}$，便可以得到答案的位数$l= \lfloor \frac{n}{C_{min}} \rfloor$。

决定了答案的位数后，我们从1到$l$枚举，对于每一位，我们从后往前枚举(因为要使答案最大化，则应尽量选靠后的数字)题中给出的$9$个数字，从中找到第一个符合剩余钱数条件的数。

要注意的是，不是只要找的一个数$C_i$,使得$C_i \leq$剩余的$N$即可。若后面的数不足以凑出足够的位数，那么这个数就无法达到应有的位数。因此，在考虑一个数$C_i$时，应该考虑给后面留下足够多的钱，即：

if(c*(len-i)+a[j]<=n)
//c为C数组中最小的数，len-i为剩余的位数，j为枚举的9个数，n为剩余的钱数。

另外，目标数$X$可能不适用于64位整型数，因此答案要用$string$类型存储。

完美解决。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n;
int a[10],c=0x3f3f3f3f; //c为C数组中最小的数
int main()
{
    cin>>n;
    for(int i=1;i<=9;i++){
        scanf("%d",&a[i]);
        c=min(c,a[i]); //找到最小数
    }
    int len=n/c; //len为答案的位数
    string ans=""; //string储存答案
    for(int i=1;i<=len;i++) //枚举位数
        for(int j=9;j>=1;j--) //枚举数字
            if((long long)(c*(len-i))+a[j]<=n){ //注意两个数相乘可能会爆int,因此强转成long long
                ans+=(j+'0'); //ans=ans*10+j
                n-=a[j]; //n为剩余的钱数
                break;
            }
    cout<<ans;
    return 0;
}

完结撒花~