带权路径长度
题目描述
给定n个权值作为n个叶子结点，构造哈夫曼树, 求其带权路径长度。
输入
输入由多组数据组成。
每组数据分成两行。第一行仅一个整数n（2<=n<=100000)。第二行有n个空格分开的权值，值范围在[1,1000000000]之间。
输出
对于每组测试数据，输出一行，即其对应哈夫曼树的带权路径长度对1000000007取模。
样例输入
4
7 5 2 4
8
5 29 7 8 14 23 3 11
样例输出
35
271
提示
注意运算溢出
解决方案
点击查看代码
#include
using namespace std;
typedef long long ll;
int main()
{
ll n;
ll a[100001];
while(cin>>n)
{
priority_queue, greater > p;
if(!p.empty())
p.pop();
for (ll i=0; i>a[i];
p.push(a[i]);
}
long long res = 0;
for(ll i=0;i