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

zifeiy 2018-04-15 原文

题目链接：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;
}