2023.11.3 做题记录

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