[CF2147D] Game on Array 题解

考虑

a_i

均为偶数的情况，此时 Bob 可以通过重复 Alice 上一次的操作来最大化自己的分数，此时两人分数均为

\displaystyle x=\frac{\sum a_i}{2}

，证明：若 Bob 没有重复 Alice 的操作，则 Alice 可以通过重复 Bob 的操作，让自己的分数至少为

x

。于是 Bob 重复 Alice 的操作一定不劣。

再考虑有奇数的情况。注意到对奇数进行一次操作后就变成偶数了，于是最开始 Alice 和 Bob 贪心地给每个奇数进行一次操作就转为了全是偶数的情况。

时间复杂度为排序的

\mathcal{O}(n\log n)

。

code

CPP

#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const ll maxn=1000007,ee=1e18,p=998244353;
ll n,a[maxn],s,su;
vector<ll> vec;
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll T=1; cin>>T;
    for(;T--;){
        cin>>n,s=su=0,vec.clear();
        for(ll i=1;i<=n;i++) cin>>a[i],su+=a[i];
        sort(a+1,a+1+n);
        for(ll l=1,r;l<=n;l=r+1){
            for(r=l;r<=n&&a[r]==a[l];r++);
            r--;
            if(a[l]&1) vec.pb(r-l+1);
            s+=(a[l]>>1)*(r-l+1);
        }
        sort(vec.begin(),vec.end(),greater<ll>());
        for(ll i=0;i<vec.size();i+=2) s+=vec[i];
        cout<<s<<" "<<su-s<<"\n";
    }
    return 0;
}

[CF2147D] Game on Array 题解

文章操作

相关推荐

评论

[CF2147D] Game on Array 题解