Construct an expanded binary tree with nexternal nodes, each external node Ki related to a weight Wi, which minimizes thesum of the external path length of leaf: Min( W1 * L1 + W2 * L2 + W3 * L3 + … + Wn * Ln)
Wi: the weight of each node
Li: the path length betweenthe root and the ith external node. Compute to minimize the sum of the external path length

Input

The first line is an integer n. n represents the number of external nodes(2<=n<=100). Input n integers in the second line, which represent the weight of each external node.

Output

Output the minimum sum of external path length.

Sample Input

4
1 1 3 5

Sample Output

17

----------------------------------------------------------------------------------------------------

题意：输出哈夫曼树的WPL。

应用数据类型：优先队列 priority_queue

#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int n, w;
    int a, b;
    int wpl;
    
    while(~scanf("%d", &n)){
        priority_queue<int, vector<int>, greater<int> > pq; // 递增排列
        for (int i = 0; i < n; i++){
            scanf("%d", &w);
            pq.push(w);
        }
        wpl = 0;
        while (pq.size() > 1){ 
            a = pq.top(); // 取最小的两个元素赋值于 a, b
            pq.pop();
            b = pq.top();
            pq.pop();
            wpl += a + b;
            pq.push(a+b);
        }
        printf("%d\n", wpl);
    }
    
    return 0;
}