CF388C Fox and Card Game

基于观察可以发现，双方都一定能保证取到每一列靠近自己的 \(\lfloor \frac{k}{2} \rfloor\) 个元素。

那么一旦一个人想要取另一个人能必然能取的部分，另一个人必然可以不让其取到。

因此，一个人去取对方一定能取到的部分是无意义的。

因此双方的策略必然都是先将靠近自身的 \(\lfloor \frac{k}{2} \rfloor\) 个元素取完，在抢中间剩下的元素。

那么对于最后剩下的元素，每次贪心的选择一定是最优的，因此双方的选择必然都是每次选取当前最大的元素。

那么我们按照这个流程模拟即可，复杂度 \(O(\sum s_i + n \log n)\)。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for (int i = l; i <= r; ++i)

#define dep(i, l, r) for (int i = r; i >= l; --i)

const int N = 100 + 5;

int n, m, s, x, A, B, a[N];

int read() {

    char c; int x = 0, f = 1;

    c = getchar();

    while (c > '9' || c < '0') { if(c == '-') f = -1; c = getchar();}

    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int main() {

    n = read();

    rep(i, 1, n) {

        s = read();

        if(s & 1) {

            rep(j, 1, s / 2) A += read();

            a[++m] = read();

            rep(j, 1, s / 2) B += read();

        }

        else {

            rep(j, 1, s / 2) A += read();

            rep(j, 1, s / 2) B += read();

        }

    }

    sort(a + 1, a + m + 1);

    dep(i, 1, m) {

        if((m - i + 1) & 1) A += a[i];

        else B += a[i];

    }

    printf("%d %d", A, B);

    return 0;

}

巴特西

CF388C Fox and Card Game

最新文章

热门文章