题解：CF2147D Game on Array

lkjzyd20 · 2025-10-18 11:08:22 · 题解

题解：CF2147D Game on Array

我们思考有哪些是两个人都可以获得的分数，容易发现，两个人都会优先选择奇数，因为考虑奇偶性，那么偶数的情况下，两个人获得的分数都是一样的。如果选择奇数的话，那么两个人就会有先后手的分差。

我们记录所有的奇数从大到小排序 a_1>a_2>a_3\dots a_n，对于先手的 Alice 她肯定一开始会选择 a_1，然后她就获得了先手的分数，但是这样 Bob 就有下次先手的机会，他肯定选择 a_2，两人的分数差距就这样你来我往的先后手，得到的分数。

对于统计两人总共的分数，我们把偶数的分数两人平分加上两个人在奇数你来我往的分数即可。

#include<bits/stdc++.h>
#define int long long
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
int n;
map<int,int>mp;
void solve(){
    cin>>n;
    vector<int>s;
    mp.clear();
    rep(i,1,n){
        int x; cin>>x;
        ++mp[x];
    }
    for(auto v:mp){
        if(v.first&1) s.push_back(v.second);
    }
    sort(s.begin(),s.end(),greater<int>());
    int f=1,ans1=0,ans2=0;
    for(auto v:s){
        if(f) ans1+=v,f=0;
        else ans2+=v,f=1;
    }
    for(auto v:mp){
        ans1+=(v.first/2)*v.second;
        ans2+=(v.first/2)*v.second;
    }
    cout<<ans1<<' '<<ans2<<'\n';
}
signed main() {
    int Q; cin>>Q;
    for(;Q;--Q){
        solve();
    }
    return 0;
}