题目来源，牛客练习赛20 F题

链接：https://www.nowcoder.com/acm/contest/128/F
来源：牛客网

题目描述

托米发现了一种新的游戏–填数字!
每填写一次数字(1≤ i≤9)需要花费ai枚金币,托米总共有n枚金币.
托米想知道他能得到的最大数字是多少.
如果填不了请输出-1。
不需要用完所有金币

输入描述:

第一行一个数字n,表示金币总数.
第二行9个正整数,第i个数字表示填写一次数字i所需要的金币数.

输出描述:

输出满足条件的最大数字.

示例1

输入
5
5 4 3 2 1 2 3 4 5
输出
55555

示例2

输入
2
9 11 1 12 5 8 9 10 6
输出
33

示例3

输入
0
1 1 1 1 1 1 1 1 1
输出
-1
备注:
0≤ n≤ 106
1≤ ai≤ 105

思路分析

第一反应，排序+遍历，傻瓜做法，结果WA一直45%，后来大佬给了一个案例才知道错了，
10
3 10 10 10 10 10 10 10 4
傻瓜做法答案是111，但是正确答案应该是911，所以正确方法应该是先找到最小金币的数字，然后判断是否可以在他的基础上增大，直接上AC代码。

AC代码

#include<iostream>
using namespace std;
int main()
{
    int n,que[10],min=999999,f;
    cin>>n;
    for (int i=1;i<10;i++)
    {
        cin>>que[i];
        if (min>=que[i])
        {
            min=que[i];
            f=i;
        }
    }
    int k=n/min;  //k是数字的个数 
    n-=k*min;   //n是剩余金币数 
    if (k==0)
    cout<<"-1"; 
    else
    {
        for (int i=9;i>f;i--)
        {
            while ((n+min)>=que[i])
            {
                cout<<i;
                k--;  //减去一个数字f 
                n-=que[i]-min;  //增加一个数字i 
            }
        }
        for (int i=0;i<k;i++)//输出剩下的数字f
        cout<<f; 
    }
}

WA 45%代码

#include<iostream>
#include<algorithm>
using namespace std;
int book[10],f=0;
typedef struct 
{
    int data;
    int flag;
}Node;
int cmp(Node a,Node b)
{
    if (a.data!=b.data)
    return a.data<b.data;
    else
    return a.flag>b.flag;
}
int main()
{
    int n;
    cin>>n;
    Node que[10];
    for (int i=1;i<10;i++)
    {
        cin>>que[i].data;
        que[i].flag=i;
    }
    sort(que+1,que+10,cmp);
    for (int i=1;i<10;i++)
    {
        if (n/que[i].data==0)
        break;
        book[que[i].flag]+=n/que[i].data;
        n%=que[i].data;
    }
    for (int i=9;i>0;i--)
    {
        for (int j=0;j<book[i];j++)
        {
            cout<<i;
            f=1;
        }
    }
    if (f==0)
    cout<<"-1";
}