首先貪心顯然是要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); }
沒有留言:
張貼留言