Codeforces 388C Fox and Card Game (贪心博弈)

Codeforces Round #228 (Div. 1)

题目链接：C. Fox and Card Game

Input

Output

Examples

output

input

output

input

output

input

output

Note

Solution

题意

给定 \(n\) 叠牌，第 \(i\) 叠牌有 \(s_i\) 张，第 \(k\) 张牌的值为 \(c_k\)。

Ciel 先手，每次选择一叠牌，拿走最上面的一张牌，Jiro 后手，每次选择一叠牌，拿走最下面的一张牌。

求两者在采取最优策略的情况下各自的分数。

题解

贪心博弈。如果一叠牌的数量是偶数，那么两个人各自取一半，如果是奇数，则中间的一叠牌单独取，其余的牌一人一半。

对所有的中间的牌排序后再轮流取。

Code

#include <bits/stdc++.h>

using namespace std;

vector<int> a;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0);

    int n;

    cin >> n;

    int sum1 = 0, sum2 = 0;

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

        int k, x;

        cin >> k;

        for(int j = 1; j <= k / 2; ++j) {

            cin >> x;

            sum1 += x;

        }

        if(k & 1) {

            cin >> x;

            a.push_back(x);

        }

        for(int j = 1; j <= k / 2; ++j) {

            cin >> x;

            sum2 += x;

        }

    }

    sort(a.begin(), a.end(), [](int a, int b){return a > b;});

    for(int i = 0; i < a.size(); ++i) {

        if(i & 1) {

            sum2 += a[i];

        } else {

            sum1 += a[i];

        }

    }

    printf("%d %d\n", sum1, sum2);

    return 0;

}