CodeForces 884D---Boxes And Balls（哈夫曼樹）

傳送門：https://codeforces.com/problemset/problem/884/D

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.

Input

3

1 2 3

Output

6

Input

4

2 3 4 5

Output

19

思路：

先把大的分出去，懲罰的更少，到底是分2個還是分3個怎麼選擇，分3個的情況當然是最佳的，那麼什麼時候分兩個，怎麼分？當n是偶數的時候，加入一個0，然後就能一直分3個。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <string>
#include <sstream>
#include <stack>
#include <queue>
#include <map>

using namespace std;
const int inf=0x3f3f3f3f;
const int MAX=2e5+5;
int n,sum;
long long wpl;
int num;
priority_queue<long long,vector<long long>,greater<long long> >q;
bool cmp(int a,int b){
	return a>b;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>num;
		q.push(num);
	}
	if(!(n&1))	q.push(0);
	while(q.size()>1){
		long long  min1=q.top();q.pop();
		long long  min2=q.top();q.pop();
		long long  min3=q.top();q.pop();
		q.push(min1+min2+min3);
		wpl+=min1+min2+min3;
	}
	cout<<wpl<<endl;
	return 0;
}