2019 Multi-University Training Contest 6

1012 Stay Real

直接贪心就可以了，每次取最大那个。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int h[100005];
int d[100005];

priority_queue<pair<int,int> >pq;

int main() {
#ifdef Inko
    freopen("Inko.in", "r", stdin);
#endif // Inko
    int T;
    while(~scanf("%d", &T)) {
        while(T--){
            int n;
            scanf("%d",&n);
            for(int i=1;i<=n;++i){
                scanf("%d",&h[i]);
                if(i!=1)
                    ++d[i/2];
            }
            ll sum1=0,sum2=0;
            for(int i=1;i<=n;++i){
                if(d[i]==0)
                    pq.push({h[i],i});
            }

            bool f1=true;
            while(!pq.empty()){
                if(f1){
                    sum1+=pq.top().first;
                    int p=pq.top().second/2;
                    pq.pop();
                    d[p]--;
                    if(d[p]==0)
                        pq.push({h[p],p});
                }
                else{
                    sum2+=pq.top().first;
                    int p=pq.top().second/2;
                    pq.pop();
                    d[p]--;
                    if(d[p]==0)
                        pq.push({h[p],p});
                }
                f1=!f1;
            }
            printf("%lld %lld
",sum1,sum2);
        }
    }
}