牛客练习赛43D（贪心）

有生之年我居然也能不看题解做出来题QAQ……

发现c、d是0、1序列而不是随机数列说明有蹊跷，于是发现负数直接配0，正数配1即可。不知道哪个最小，那就全求一下吧……我的做法的坑点是数正好为1时不可以选。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 5;

const ll inf = 1e18;

int n, a[maxn], b[maxn], ansc[maxn], ansd[maxn];

ll ans = -inf;

void solve(int *a, int *b, int *ansc, int *ansd) {

    int c[maxn], d[maxn], t[maxn];

    ll sum = 0, C = 0;

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

        if (a[i] > 1) {

            c[i] = 1;

            C++;

            sum += a[i];

        } else {

            c[i] = 0;

        }

    }

    ll k = 0, D = 0;

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

        t[i] = i;

        d[i] = 0;

    }

    sort(t + 1, t + 1 + n, [&](int x, int y) { return b[x] > b[y]; });

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

        int tmp = t[i];

        if (b[tmp] <= 1)    break;

        d[tmp] = 1;

        D++;

        k += b[tmp];

        if (k >= sum)   break;

    }

    if (k >= sum) {

        ll calc = sum - C - D;

        if (calc > ans) {

            ans = calc;

            memcpy(ansc, c, sizeof c);

            memcpy(ansd, d, sizeof d);

        }

    }

}

int main() {

    scanf("%d", &n);

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

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

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

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

    solve(a, b, ansc, ansd);

    solve(b, a, ansd, ansc);

    printf("%lld\n", ans);

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

        printf("%d%c", ansc[i], " \n"[i == n]);

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

        printf("%d%c", ansd[i], " \n"[i == n]);

}

巴特西

牛客练习赛43D（贪心）

最新文章

热门文章