【贪心】Codeforces 349B.Color the Fence题解

时间:2024-10-21 21:35:44

题目链接:http://codeforces.com/problemset/problem/349/B

题目大意

小明要从9个数字(1,2,……,9)去除一些数字拼接成一个数字,是的这个数字最大。

但是小明每取一个数字i就会消耗a[i]点体力,小明目前总共有v点体力。

举个例子:

小明如果有5点体力,而a[1]到a[9]的数值依次为:

5 4 3 2 1 2 3 4 5

那么最好的办法就是取5次数字5,因为a[5]=1最小,所以最终得到的数字是11111,比起其他的取数策略所得到的数字都要大。

分析

这道题目可以采用贪心的策略。

要让数字尽可能地大,我们首先想到的应该是让这个数字尽可能地“长”,所以我们会下意识的去选 a[i]最小并且i最大 的那个数字i,我们在这里设这个i为x,表示a[x]是数组a中最小的数的坐标组成的集合中(因为a[i]==min(a[i])的数可能不止一个)对应的坐标最大的那个坐标。

如果这个策略导致v % a[i] == 0 的话,那么这个结果就是我们想要的结果。

但是还存在一个情况,如果v == 17 && i == 8并且a[9] == a[8]+1的话,我们采用之前的方法得到的是“88”,但是其实结果可以是“98”,因为我们可以用“9”代替结果中的第一个“8”。

所以在通过初始方法获得基本数字之后,我们还要从9遍历到x+1,看看这些数字是否可以一次代替首位的x,第二位的x,……,直到不能替代为止。

还有一点可能感到困惑的情况是:可能会有同学会觉得这个方法会有错误,其实我们是可以推断的,因为a[x]已经是最小的了,所以最终结果的位数肯定是⌊v / a[x]⌋,在这种情况下,我们只需考虑尽可能地让这个数字的越高位尽可能地大即可,这也是贪心算法所在。

实现

C++代码实现:

#include <iostream>
using namespace std;
int v, a[10], x = 1, y = 0;
int main() {
cin >> v;
for (int i = 1; i <= 9; i ++) {
cin >> a[i];
if (a[i] <= a[x])
x = i;
}
int left = v % a[x];
int cnt = v / a[x];
for (int i = 9; i > x && cnt;) {
if (a[i] <= left + a[x]) {
cout << i;
cnt --;
left -= a[i] - a[x];
}
else {
i --;
}
}
if (cnt == 0) {
cout << -1 << endl;
} else {
while (cnt --) {
cout << x;
}
cout << endl;
}
return 0;
}