ACM Color the fence

Color the fence

时间限制：1000 ms  |  内存限制：65535 KB

难度：2

描述

Tom has fallen in love with Mary. Now Tom wants to show his love and write a number on the fence opposite to 

Mary’s house. Tom thinks that the larger the numbers is, the more chance to win Mary’s heart he has.

Unfortunately, Tom could only get V liters paint. He did the math and concluded that digit i requires ai liters paint. 

输入

There are multiple test cases.

Each case the first line contains a nonnegative integer V(0≤V≤10^6).

The second line contains nine positive integers a1,a2,……，a9(1≤ai≤10^5).

输出

Printf the maximum number Tom can write on the fence. If he has too little paint for any digit, print -1.

样例输入

5
5 4 3 2 1 2 3 4 5
2
9 11 1 12 5 8 9 10 6      

样例输出

55555
33
本题题意是给V升的油漆，以及1-9每个数字需要的油漆，问用这些油漆能刷出的最大的数字？
如给得第一个测试用例，有5升油漆，数字5需要1升油漆，故把数字5刷5次得到的数字最大
但存在这样的测试用例
9
5 4 2 3 5 4 6 4 5
则全用来刷数字3的话，为3333，还剩1升油漆
如果刷3个数字2，还剩3升用来刷数字4，则结果为4333，比全用来刷数字2大
同时还存在一种测试用例
8
5 4 3 2 5 4 6 1 1
有油漆相同的情况，应该选择数字最大的
本题还未考虑下面这种情况，参考codeforce给出的测试用例才知道
      

898207
99745 99746 99748 99752 99760 99776 99808 99872 100000
结果为987654321

      

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int v;
    while(cin >> v){
        vector<int> num(10,0);
        int minIndex = 1;
        for(int i = 1 ; i < 10; ++ i){
            cin >> num[i];
            if(num[minIndex]>=num[i]) minIndex = i;
        }
        if(v < num[minIndex]) cout<<-1<<endl;
        else if(v%num[minIndex] == 0) cout<<string(v/num[minIndex],'0'+minIndex)<<endl;
        else{
            int cnt = v/num[minIndex], remain = v%num[minIndex];
            for(int i = 0 ; i < cnt; ++ i){
                for(int j = 9 ; j > 0; -- j){
                    if(j <= minIndex){
                        cout<<minIndex;
                        break;
                    }
                    if(remain-(num[j]-num[minIndex]) >= 0){
                        remain -=(num[j]-num[minIndex]);
                        cout<<j;
                        break;
                    }
                }
            }
            cout<<endl;
        }
    }
}