Codeforces 884D：合并果子

題意：現在在1盒子中有N中顔色的求各ai個，要求操作若幹次使得顔色i的球全部進入i盒子中，操作為：從某個盒子中取出所有的球，花費是取出球的總個數，然後把這些球分成k堆，放到k個空的盒子中去，k=2或者3.求最小花費。

題解：反過來想，就是合并果子嘛。求一個帶權路徑和最小值，就是3-哈夫曼樹。顯然3-哈夫曼樹比2-哈夫曼樹更優，但是2-哈夫曼樹對于任意個數的果子都可以構造出來，因為每次2->1，每次減少一個果子。但是3-哈夫曼樹，每次3->1，每次減少兩個，這就要求果子總數為奇數，如果給定的果子總數是偶數，那麼就加一個0果子進去就完事了。

Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+100;
typedef long long LL;
priority_queue<LL,vector<LL>,greater<LL> >pq;
int n;
LL sum =0;
int main(){
	scanf("%d",&n);
	for (int i=0;i<n;i++){
		int val;
		scanf ("%d",&val);
		pq.push(val);
	}
	if (n&1);else pq.push(0);
	while (pq.size()>1){
		LL temp = pq.top();pq.pop();
		temp+=pq.top();pq.pop();
		temp+=pq.top();pq.pop();
		sum+=temp;
		pq.push(temp);
	}
	cout<<sum<<endl;
	return 0;
}