新材料 东莞网站建设,网站分享的功能怎么做的,PHP网站开发与管理设计心得,邯郸做wap网站哈夫曼树#xff0c;第一行输入一个数n#xff0c;表示叶结点的个数。需要用这些叶结点生成哈夫曼树#xff0c;根据哈夫曼树的概念#xff0c;这些结点有权值#xff0c;即weight#xff0c;题目需要输出所有结点的值与权值的乘积之和的最小值。
输入描述:
输入有多组…哈夫曼树第一行输入一个数n表示叶结点的个数。需要用这些叶结点生成哈夫曼树根据哈夫曼树的概念这些结点有权值即weight题目需要输出所有结点的值与权值的乘积之和的最小值。
输入描述:
输入有多组数据。 每组第一行输入一个数n接着输入n个叶节点叶节点权值不超过1002n1000。输出描述:
输出权值。
示例1
输入
5
1 2 2 5 9输出
37#include iostream
#include queueusing namespace std;
//叶子结点到根 最小带权路径之和
int main() {//优先队列存储叶子结点 找最小值priority_queueint pqueue;//默认大根堆 取相反数int n;scanf(%d,n);for(int i0;in;i){int leaf;scanf(%d,leaf);//取得pqueue.push(-leaf);//插入}//带权路径和int res0;//存储带权路径和的中间结果while(pqueue.size()1){int leaf1pqueue.top();//取出来pqueue.pop();int leaf2pqueue.top();pqueue.pop();//计算resresleaf1leaf2;//构成的新子树插入到原集合中pqueue.push(leaf1leaf2);}printf(%d\n,-res);//构建完成哈夫曼树输出结果return 0;
}
