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;
        }
    }
}