CF-388C. Fox and Card Game（博弈、贪心）

CF传送门

洛谷传送门

---

解题思路

贪心：若序列长度为偶数，则每人拿一半，若为奇数，则所有奇数序列的中间元素从大到小排序，两人依次拿，剩下的两边的也是一人一半。

证明（感性）：若对方想要抢走你那一半的元素，说明你那一半的元素肯定更大，你不可能让对面抢去，所以每个人都守着自己这一半的元素。

真不明白为啥紫题。

AC代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,ans1,ans2,cnt,x,a[10005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>m;
        for(int j=1;j<=m/2;j++){
            cin>>x;
            ans1+=x;
        }
        if(m&1){
            cin>>a[++cnt];
        }
        for(int j=1;j<=m/2;j++){
            cin>>x;
            ans2+=x;
        }
    }
    sort(a+1,a+cnt+1);
    for(int i=cnt;i>=1;i--){
        if((cnt-i)&1) ans2+=a[i];
        else ans1+=a[i];
    }
    cout<<ans1<<" "<<ans2;
    return 0;
}