Codeforces 890 D. Boxes And Balls （哈夫曼+优先队列+逆向思维）

#include<queue>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn=200010;
priority_queue<ll,vector<ll>,greater<ll> >q;
ll a[maxn];
int main() {
	int N;
	ll ans=0,tmp;
	scanf("%d",&N);
	for(int i=1; i<=N; i++) {
		scanf("%I64d",&a[i]);
		q.push(a[i]);
	}
	if(N==1) {
		printf("0\n");
		return 0;
	}
	if(N%2==0) q.push(0);
	while(q.size()>3) {
		tmp=q.top();
		q.pop();
		tmp+=q.top();
		q.pop();
		tmp+=q.top();
		q.pop();
		ans+=tmp;
		q.push(tmp);
	}
	while(!q.empty()) {
		ans+=q.top();
		q.pop();
	}
	cout<<ans<<endl;
	return 0;
}