CF349B *1700
\(Igor\)深深爱上了\(Tanya\). 现在, \(Igor\)想表达他的爱意, 他便在\(Tanya\)家对面的墙上写下一串数字. \(Igor\)认为, 数字写得越大, \(Tanya\)越喜欢他. 不幸的是, 他只有\(v\)升油漆, 每个数字都会花掉一定的油漆\(a_i\). \(Igor\)不喜欢\(0\) 所以数中不会出现\(0\). 问\(Igor\)能得到的最大的数是多少.
显然数的长度越大这个数越大，先用最少花费的数求出最大长度，然后从高位到低位挨着尝试替换即可。
#include<bits/stdc++.h>
#define lson rt << 1
#define rson rt << 1 | 1
using namespace std;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
inline int read() {
int res = 0, f = 0; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) f |= (ch == '-');
for(; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + (ch - '0');
return f ? -res : res;
}
int V;
pair <int, int> a[15];
int ans[N << 3];
signed main() {
V = read();
for(int i = 1; i <= 9; i++) a[i].first = read(), a[i].second = i;
int MinFy = INT_MAX, Minwz = 0;
for(int i = 1; i <= 9; i++) {
if(MinFy > a[i].first) MinFy = a[i].first, Minwz = a[i].second;
if(MinFy == a[i].first) Minwz = a[i].second;
}
int Max_Len = V / MinFy;
V -= Max_Len * MinFy;
for(int i = 1; i <= Max_Len; i++) ans[i] = Minwz;
for(int i = 1; i <= Max_Len; i++) {
for(int j = 9; j > Minwz; j--) {
if(V + MinFy >= a[j].first) {
V += MinFy, V -= a[j].first, ans[i] = j;
break;
}
}
}
if(!Max_Len) return puts("-1"), 0;
for(int i = 1; i <= Max_Len; i++) cout << ans[i];
return 0;
}