哈夫曼树
哈夫曼树
https://www.nowcoder.com/practice/162753046d5f47c7aac01a5b2fcda155?tpId=40&rp=1&ru=%2Fta%2Fkaoyan&qru=%2Fta%2Fkaoyan%2Fquestion-ranking&gioEnter=menu
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main(){
int n;
while(scanf("%d",&n)!=EOF){
priority_queue<int ,vector<int>,greater<int>> myPriorityQueue;
while(n--){
int x;
scanf("%d",&x);
myPriorityQueue.push(x); //把输入的权值输入到队列中
}
int answer=0; //answer==WPL
while(myPriorityQueue.size() > 1){
int a=myPriorityQueue.top();
myPriorityQueue.pop();
int b=myPriorityQueue.top();
myPriorityQueue.pop();
answer += a+b;
myPriorityQueue.push(a+b); //把算的的answer放入队列中在运算
}
printf("%d\n",answer);
}
return 0;
}