Description
Ivan has n different boxes. The first of them contains some balls of n different colors.
Ivan wants to play a strange game. He wants to distribute the balls into boxes in such a way that for every i (1?≤?i?≤?n) i-th box will contain all balls with color i.
In order to do this, Ivan will make some turns. Each turn he does the following:
Ivan chooses any non-empty box and takes all balls from this box;
Then Ivan chooses any k empty boxes (the box from the first step becomes empty, and Ivan is allowed to choose it), separates the balls he took on the previous step into k non-empty groups and puts each group into one of the boxes. He should put each group into a separate box. He can choose either k?=?2 or k?=?3.
The penalty of the turn is the number of balls Ivan takes from the box during the first step of the turn. And penalty of the game is the total penalty of turns made by Ivan until he distributes all balls to corresponding boxes.
Help Ivan to determine the minimum possible penalty of the game!
Input
The first line contains one integer number n (1?≤?n?≤?200000) — the number of boxes and colors.
The second line contains n integer numbers a 1, a 2, …, a n (1?≤?a i?≤?109), where a i is the number of balls with color i.
Output
Print one number — the minimum possible penalty of the game.
Examples
input
3
1 2 3
output
6
input
4
2 3 4 5
output
19
题意：
给你n个盒子，n种颜色的球，起初的球全部放到第一个盒子里面，进行以下操作
1.每次取出颜色不是相同盒子里的球，同时得到相应的球数量的惩罚
2.在第一步中选择的球，分成k个集合，k=2或者3，这k个集合需要将相同的颜色放到1个集合或者两个集合中，其余颜色放到另一个集合中 ，然后将这k个集合分别放到k个盒子里。 重复上面两个操作直到将相同颜色的球分到每个盒子中 。
思路：
本题是哈夫曼树的反向思维，其实是从哈夫曼树的根节点往子节点迭代，但是这儿需要注意因为每次选择两个或者三个盒子来装，我们当然选择三个盒子来装是最优的，如果选择两个盒子每次只能分一个相同颜色的球出来，这样累计到得乘法就越多。
但是当n为偶数时，我们最后一次分可以采用分成两个集合，算法实现的时候判断n为偶数时，压入0即可。
AC代码
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
priority_queue<ll, vector<ll>, greater<ll> > q;
int main(){ll wpl=0;int n,x;cin>>n;for(int i=0;i<n;i++) cin>>x,q.push(x);if((n&1) == 0) q.push(0);//如果是偶数，最后一次选择k=2.while(q.size()>1){ll min1 = q.top(); q.pop();ll min2 = q.top(); q.pop();ll min3 = q.top(); q.pop();wpl+=min1+min2+min3;q.push(min1+min2+min3);}q.pop(); cout<<wpl<<endl;return 0;
}