Learning-Algorithm-CPP/1082.cpp at main · woodart8/Learning-Algorithm-CPP · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N,M;
vector<pair<int, int>> menu;
int p[10];

int main() {
    cin >> N;
    for(int i=0; i<N; i++) {
        cin >> p[i];
        menu.push_back({p[i], i});
    }
    cin >> M;

    sort(menu.begin(), menu.end());

    string s = "";
    if(N == 1) {
        cout << "0";
        return 0;
    }

    if(menu[0].second != 0){
        int cnt = M/menu[0].first;
        for(int i=0; i<cnt; i++) s += to_string(menu[0].second);
        M -= cnt * menu[0].first;
    }else{
        int m = M - menu[1].first;
        if(m<0) {
            cout << "0";
            return 0;
        }
        s += to_string(menu[1].second);
        int cnt = m/menu[0].first;
        for(int i=0; i<cnt; i++) s += to_string(menu[0].second);
        M  = m - cnt * menu[0].first;
    }

    for(int i=0; i<s.size(); i++){
        bool ok = false;
        int cur = p[s[i] - '0'];
        for(int j=N-1; j>=0; j--){
            if(M - (p[j]-cur) >= 0){
                M -= p[j]-cur;
                ok = 1;
                s[i] = j + '0';
            }
            if(ok) break;
        }
        if(!ok) break;
    }

    cout << s;
    return 0;
}