赞
踩
哈夫曼树,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。
输入描述:
输入有多组数据。 每组第一行输入一个数n,接着输入n个叶节点(叶节点权值不超过100,2<=n<=1000)。
输出描述:
输出权值。
示例1
输入
5 1 2 2 5 9
输出
37
一道哈夫曼树签到题。
- #include<iostream>
- #include<vector>
- #include<cmath>
- #include<queue>
- using namespace std;
- int main()
- {
- int n;
- while(cin>>n)
- {
- int a;
- priority_queue<int,vector<int>,greater<int> >p;
- for(int i=0;i<n;i++)
- {
- cin>>a;
- p.push(a);
- }
- int m1,m2;
- int sum=0;
- while(p.size()>1)
- {
- m1=p.top();
- p.pop();
- m2=p.top();
- p.pop();
- sum=sum+m1+m2;
- p.push(m1+m2);
- }
- cout<<sum<<endl;
- }
- return 0;
- }
2020.4.13
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。