一、题目内容

题目描述

It’s universally acknowledged that there’re innumerable trees in the campus of HUST.
People like to play games under the tree, and SWH is exactly fond of one strange card game. In the game players are given some piles of cards with scores. Two players will take turns to draw a card from one pile and get the score of the card. Each player can choose the pile arbitrarily. However, the strange thing is that the player draws first can only draw a card from the top of one pile, and the player played second from the bottom. The game ends when all piles become empty. Now SWH and his friend LLY is going to play the game and SWH plays first. Both of them want to maximize his own score. Can you tell how many scores they will get finally?

输入描述

First line you are given an integer n(1≤n≤100), indicating the number of decks.
Then n line follows. Each i-th line contains an integer m_i (1≤m_i≤100), the number of cards in i-th pile, then m_i number follow s1,s2,...sk,...sm(0≤si≤1000)，the score of each card. And we see the first card as “top”, the last card as “bottom”.

输出描述

Two integers, the final score of SWH and LLY.

示例1

输入

2
2 5 10
1 20

输出

25 10

二、解题思路

依题意，这个纸牌游戏的特点是：有两个玩家，先抽的玩家从任意牌堆顶部抽取，后抽的玩家从任意牌堆的底部抽取，两个玩家存在竞争关系，目标是获得最高分数。玩家在抽取纸牌时，偶数堆则刚好平分，奇数堆则余1张纸牌，假如两人都希望获得最高分，那么只存在一种可能，玩家将所有的偶数牌堆分完，然后再抽取奇数牌堆时，每次保留奇数牌堆剩下的一张并存入数组，最后将数组按照纸牌牌面从大到小排序，两个玩家按排序的顺序依次抽取纸牌即可获得最大（牌堆是不能确认中间纸牌牌面大小的）。

代码实操

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int mod  = 1e9 + 7;
vector<ll> rest_a;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    while(cin >> n) {
        int m;
        ll ans1 = 0, ans2 = 0, num;
        while(n--) {
            cin >> m;
            for(int i = 0; i < m; i++) {
                cin >> num;
                if (i < m / 2) {
                    ans2 += num;
                } else if(m % 2 == 1 && m / 2 == i) {
                    rest_a.push_back(num);
                } else {
                    ans1 += num;
                }
            }
        }
        sort(rest_a.begin(),rest_a.end());
        reverse(rest_a.begin(),rest_a.end());
        for(int i = 0; i < rest_a.size(); i++) {
            if (i & 1) {
                ans1 += rest_a[i];
            } else {
                ans2 += rest_a[i];
            }
        }
        cout << ans2 << " " << ans1 << endl;
    }
    return 0;
}

感兴趣的同学可以前往牛客网一起AC。

Cards Game