Codeforces Round #693 (Div. 3) D. Even-Odd Game

D. Even-Odd Game

题目分析

题意：请去看题面

这是一道博弈论+贪心的题目。输入一串数字之后，Bob和Alice可以任意选择其中的一个数字，来让自己的得分最高，那么我们不妨将输入的数字排一下序，根据得分规则，他们可以选择拿走能让自己加分的数字来提高自己的分数，也可以选择拿走不能让自己加分的数字，破坏能让对手加分的数字。

所以可以让选手每次选择最大的数字，如果能让自己得分，那么拿走让自己得分，如果不能自己得分，那就拿走不让对手得分，最后比较一下二者的分数即可。具体实现思路请看下方代码

AC代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
bool cmp(ll a, ll b){
    return a > b;
}
const int N = 200200;
long long q[N];
int T, n, m;
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> T;
    while(T--){
        long long Alice = 0, Bob = 0;
        cin >> n;
        for(int i = 0; i < n; i++) cin >> q[i];
        sort(q, q + n, cmp); // 当然你也可以从小到大排序
        for(int i = 0; i < n; i++){
            // 由于Alice是先手，所以 i 为偶数时是Alice的回合，为奇数是Bob的回合
            if(i % 2 == 0 && q[i] % 2 == 0) Alice += q[i];
            else if(i & 1 && (q[i] & 1)) Bob += q[i];
        }
        if(Alice > Bob) cout << "Alice" << endl;
        else if(Alice < Bob) cout << "Bob" << endl;
        else cout << "Tie" << endl;
    }

    return 0;
}