2015 多校联赛 ——HDU5350（huffman）

Problem Description

MZL is a mysterious mathematician, and he proposed a mysterious function at his young age.
Stilwell is very confused about this function, and he need your help.
First of all, given n positive integers Ai and Ai≥Ai+1.
Then, generate n positive integers Bi

B i = \sum j = i n A j

Define f(i,j) for i,j∈Z

f (i, j) = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ 0 m i n (f (i - 1, j + 1), f (i, ⌈ j 2 ⌉) + B i) 1011037 (i, j) = (1, 1) i, j \in [1, n], (i, j) \neq (1, 1) o t h e r w i s e

Find f(n,1).

Input

The first line of the input contains a single number T, the number of test cases.
For each test case, the first line contains a positive integer n, and the next line contains n positive integers Ai.
T≤100, 1≤n≤105, ∑n≤106, 1≤Ai≤104.

Output

For each test case, output f(n,1) in a line.

Sample Input

3
3
1 1 1
5
28 26 25 24 1
10
996 901 413 331 259 241 226 209 139 49

Sample Output

5
233
11037

//完全没看出来是个huffman - -！

#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<functional>
#include<queue>
typedef long long ll;
using namespace std;


int main()
{
    int T;
    int n,a;
    priority_queue<ll, vector<ll>, greater<ll> >q;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        while(!q.empty())
        {
            q.pop();
        }
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a);
            q.push(a);
        }
        ll sum = 0;
        while(!q.empty())
        {
            ll x = q.top();
            q.pop();
            if(q.empty())
            {
                continue;
            }
            ll y = q.top();
            q.pop();
            ll tmp= x + y;
            sum+=tmp;
            q.push(tmp);
        }
        printf("%I64d
",sum);
    }
    return 0;
}