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;
}