Codeforces 349B 《Color the Fence》

九月 30, 2018 3562

瞎贪心

题目描述

翻译来自洛谷

Igor深深爱上了Tanya. 现在, Igor想表达他的爱意, 他便在Tanya家对面的墙上写下一串数字. Igor认为, 数字写得越大, Tanya越喜欢他. 不幸的是, 他只有 v 升油漆, 每个数字都会花掉一定的油漆 a_i . Igor不喜欢 0 所以数中不会出现 0 . 问Igor能得到的最大的数是多少.

Input / Output 格式 & 样例

输入格式

第一行一个整数 v ，意义如题

第二行有九个数字 a_1,\ a_2,\ a_3,\ \dots \ ,\ a_9 ，表示第 i 个数字需要 a_i 升油漆

输出格式

一行一个整数，表示最大的Igor可以得到的数。

输入样例

Case #1:

1
2
5
5 4 3 2 1 2 3 4 5

Case #2:

1
2
2
9 11 1 12 5 8 9 10 6

Case #3:

1
2
0
1 1 1 1 1 1 1 1 1

输出样例

Case #1:

1
55555

Case #2:

1
33

Case #3:

1
-1

解析

明显的贪心

先对这个序列排序（优先队列方便快捷），再从小到大依次计算可以画出的数字和画出数字的次数

接着从9到1进行枚举，看一看有没有什么可以替换一下的，替换成花费相对最小的数字

最后输出答案数组

代码实现

玄学代码风格（雾

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterator -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)
using namespace std;

/*  Constants Start  */

/*  Constants End  */

/*  Variants Start  */

int v;

int q[10]; 
// q[i].first = variant
// q[i].second = id

int ans[10];

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;

/*  Variants End  */

namespace FastIO {
    void DEBUG(char comment[], int x) {
        cerr << comment << x << endl;
    }

    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }

    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}

int main(int argc, char *const argv[]) {
    #ifdef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
    #endif
    v = FastIO::getint();
    For (i, 1, 9) {
        q[i] = FastIO::getint();
        pq.push(std::make_pair(q[i], -i));
    }
    // 贪心选择当前最优
    while (!pq.empty()) {
        pair<int, int> pr = pq.top();
        pq.pop();
        ans[-pr.second] = v / pr.first;
        v %= pr.first;
    }
    q[0] = 2147482333;
    // 进行替换
    Bak (i, 9, 1) {
        int tmp = 0;
        Bak (j, i - 1, 1) {
            if (ans[j] && q[j] < q[tmp]) tmp = j;
        }
        if (!tmp) continue;
        while (ans[tmp] && v && v >= q[i] - q[tmp]) 
            v -= q[i] - q[tmp], ++ans[i], --ans[tmp];
    }
    bool Printed = false;
    Bak (i, 9, 1) {
        while (ans[i]) {
            FastIO::__basic_putint(i);
            --ans[i];
            Printed = true;
        }
    } 
    // 程序并没有正确答案，输出-1
    if (!Printed) puts("-1");
    return 0;
}