哈夫曼树（暑假每日一题 15）

哈夫曼树（暑假每日一题 15）

输出格式 输出一个整数，表示生成哈夫曼树的带权路径长度。

输入样例：

51 2 2 5 9

输出样例：

37

#include#include#include#define x first#define y secondusing namespace std;typedef pair PII;const int N = 2010;int n;int a[N], l[N], r[N];priority_queue, greater> q;int get(int u, int d){ if(l[u] == -1 && r[u] == -1) return a[u] * d; return get(l[u], d + 1) + get(r[u], d + 1);}int main(){ memset(l, -1, sizeof l); memset(r, -1, sizeof r); cin >> n; for(int i = 0; i < n; i++) cin >> a[i], q.push({a[i], i}); PII t1, t2; while(q.size() > 1){ t1 = q.top(), q.pop(); t2 = q.top(), q.pop(); int s = t1.x + t2.x; l[n] = t1.y, r[n] = t2.y; q.push({s, n}); n++; } PII root = q.top(); cout << get(root.y, 0) << endl; return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。