题解 CF725E 【Too Much Money】

· · 题解

一般这种任意数量的，都是只有一个或两个 都是套路

主要是太多了也做不了

这题也不例外，最多只可能加入一个硬币。

可以感性理解一下，两个硬币 a 与 b 肯定不如 a+b 来的优秀。

于是可以考虑从小到大枚举那个硬币的权值。

然后判断是否可行，如果不可行说明找到了答案。

当然直接这么做是不行的（O(nc)的复杂度）。

需要加入一些剪枝。

假设当前枚举的权值为 w

首先判断时可以预处理出比 w 大的那些物品的使用情况，因为当前物品对它们没有影响。

然后有一个很重要的，对于相同的数只扫一次，假如 x 可以使用，那么其他的 x 也可以使用，取决于当前还需要多少钱。

复杂度：O ( 能过 )

应该可以证明是正确的。

Code: 
#include <bits/stdc++.h>

const int N = 2e5 + 7;
int n, c, val[N], s[N], v[N], sum[N];

inline int read() {
    int x = 0;
    char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x;
}

int main() {
    c = read();
    n = read();
    for (int i = 1; i <= n; ++ i) {
        val[i] = read();
    }
    std::sort(val + 1, val + 1 + n);
    int tot = 1, cnt = 0;
    for (int i = 1; i <= n; ++ i) {
        if (val[i] == val[i + 1]) ++ tot;
        else v[++ cnt] = val[i], sum[cnt] = tot, tot = 1;
    }
    int x = c;
    for (int i = cnt; i >= 1; -- i) {
        if (v[i] <= x) {
            int k = x / v[i];
            k = std::min(k, sum[i]);
            x -= k * v[i];
            s[i] = x;
        } else s[i] = x;
    }
    int pos = 2, ans = 0;
    bool flag = 0;
    for (int i = v[1] + 1; i <= c; ++ i) {
        while (i > v[pos] && pos <= cnt) ++ pos;
        int x = c;
        if (pos <= cnt) x = s[pos];
        else x = c;
        bool tag = 0;
        if (i > x) continue;
        x -= i;
        if (x == 0) continue;
        for (int j = pos - 1; j >= 1; -- j) {
            if (v[j] <= x) {
                int k = x / v[j];
                k = std::min(k, sum[j]);
                x -= k * v[j];
            }
            if (x == 0) {
                tag = 1;
                break;
            }
        }
        if (!tag) {
            flag = 1;
            ans = i;
            break;
        }
    }
    if (!flag) {
        puts("Greed is good");
        return 0;
    }
    printf("%d\n", ans);
    return 0;
}