Codeforces 725E Too Much Money (看题解)

最关键的一点就是这个贪心可以在sqrt(n)级别算出答案。

因为最多有sqrt(n)个不同的数值加入。

我们可以发现最优肯定加入一个。

然后维护一个当前可以取的最大值，枚举加入的数来贪心。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N = 2e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

const double eps = 1e-;

const double PI = acos(-);

int tar, n, tot, a[N], hs[N], cnt[N], mx[N], now[N];

vector<int> vc;

bool check(int add) {

    vc.clear();

    int c = tar;

    int p = mx[c];

    while(c) {

        if(add > c) add = ;

        while(!now[p] && p) p--;

        p = min(p, mx[c]);

        if(!p && !add) break;

        if(p && hs[p] >= add) {

            vc.push_back(p);

            int v = hs[p], num = min(now[p], c / v);

            now[p] -= num;

            c -= num * v;

        } else {

            c -= add;

            add = ;

        }

    }

    for(auto& x : vc) now[x] = cnt[x];

    return c;

}

int main() {

    scanf("%d%d", &tar, &n);

    for(int i = ; i <= n; i++) {

        scanf("%d", &a[i]);

        hs[++tot] = a[i];

    }

    sort(hs + , hs + tot + );

    tot = unique(hs + , hs + tot + ) - hs - ;

    for(int i = ; i <= n; i++) cnt[lower_bound(hs + , hs + tot + , a[i]) - hs]++;

    for(int i = ; i <= tot; i++) now[i] = cnt[i];

    for(int i = ; i <= tar; i++) mx[i] = upper_bound(hs + , hs + tot + , i) - hs - ;

    for(int i = ; i <= tar; i++) {

        if(check(i)) {

            printf("%d\n", i);

            return ;

        }

    }

    puts("Greed is good");

    return ;

}

/*

*/