数据结构与算法题目集7-29——修理牧场
发布时间
阅读量：
阅读量
我的数据结构与算法题目集代码仓：https://github.com/617076674/Data-structure-and-algorithm-topic-set
原题链接：https://pintia.cn/problem-sets/15/problems/856
题目描述：
知识点：哈夫曼树
思路：利用哈夫曼树计算树的最小带权路径长度
步骤如下：
（1）初始状态下共有N个节点，节点的权值分别是给定的N个数，将它们视作N棵只有一个节点的树。
（2）合并其中根节点权值最小的两棵树，生成两棵树根节点的父节点，权值为这两个根节点的权值之和，这样树的数量就减少了一个。
（3）重复操作（2），直到只剩下一棵树为止，这棵树就是哈夫曼树。
而对于本题，只需计算最小带权路径长度即可。
时间复杂度是O(NlogN)。空间复杂度是O(N)。
C++代码：
#include<iostream>
#include<queue>
using namespace std;
int N;
priority_queue<int, vector<int>, greater<int> > pq;
int main(){
scanf("%d", &N);
int num;
for(int i = 0; i < N; i++){
scanf("%d", &num);
pq.push(num);
}
int result = 0;
while(pq.size() > 1){
int num1 = pq.top();
pq.pop();
int num2 = pq.top();
pq.pop();
int num = num1 + num2;
pq.push(num);
result += num;
}
printf("%d\n", result);
return 0;
}
C++解题报告：
全部评论 (0)
还没有任何评论哟~