BUPT-哈夫曼树

BUPT-哈夫曼树

题目链接

​​ 1 2 2 5 9

输出

复制

37

题解：

利用哈夫曼树的性质：所有叶节点权值与值的乘积和等于所有非叶节点的值之和。

#include #include using namespace std;priority_queue, greater> q;int main(){ int n; while(cin >> n){ while(q.empty() == false){ q.pop(); } for(int i = 0; i < n; i++){ int x; cin >> x; q.push(x); } int ans = 0; while(q.size() > 1){ int a = q-(); q.pop(); int b = q-(); q.pop(); ans += a + b; q.push(a + b); } cout << ans << endl; } return 0;}

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