[Codeforces 100488K][2014-2015 Samara SAU ACM ICPC Quarterfinal Qualification Contest] Two Pirates

原題連結

首先貪心顯然是要WA的，就不解釋了
困難之處在於無法知道最終兩人分別會取到什麼樣的數字集合

不妨先手動模擬一個簡單的取數字過程，一旦發現經過交換之後可以使先手的數字和更大就交換

最後就可以想成每一個Round先手先把數字都拿走，然後把目前為止他有的數字集合裡的最小數字丟給後手

可用heap或是priority_queue來實現

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int INF=(1<<30);
const int maxn=100000+5;
priority_queue<int,vector<int>,greater<int> > pq;
int a[maxn];
int main()
{
    int n;
    LL sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {scanf("%d",a+i);sum+=a[i];}
    for(int i=1;i<=n;i++)
    {
        pq.push(a[i]);
        if(i%2==0) pq.pop();
    }
    LL ans=0;
    while(!pq.empty()) {ans+=pq.top();pq.pop();}
    printf("%I64d %I64d\n",ans,sum-ans);
}