XDOJ 767 哈弗曼树
试题名称 哈弗曼树
时间限制: 1 秒
内存限制: 256KB
问题描述
假设用于通信的电文由ｎ个字符组成，字符在电文中出现的频度（权值）为w1,w2,…,wn，试根据该权值序列构造哈夫曼树，并计算该树的带权路径长度。
输入说明
第１行为ｎ的值，第２行为ｎ个整数，表示字符的出现频度。
输出说明
输出所构造哈夫曼树的带权路径长度。
输入样例
8
7 19 2 6 32 3 21 10
输出样例
261
// 2024/12/29 OK
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
priority_queue<int, vector<int>, greater<int>> q;
cin >> n;
for (int i = 0; i < n; i ++) {
int tmp;
cin >> tmp;
q.push(tmp);
}
int cnt = 0;
while (q.size() >= 2) {
int a = q.top(); q.pop();
int b = q.top(); q.pop();
int c = a + b;
cnt += c;
q.push(c);
}
cout << cnt;
return 0;
}