题解 | #哈夫曼树#

哈夫曼树

https://www.nowcoder.com/practice/162753046d5f47c7aac01a5b2fcda155

关键在于找到求解最短路径长度的规律,无需建树
#include <iostream>
#include <queue>
using namespace std;

struct hafuman {
	int value;

};

bool operator < (hafuman lhs, hafuman rhs) {
	return lhs.value > rhs.value;   //变成小根堆

}


int main() {
	int n,dot;
	while (cin >> n) {
		int a, b, res = 0 ; //res表示带权路径长度
		priority_queue<hafuman>  HafumanTree;
		for (int i = 0; i < n; i++) {
			cin >> dot;
			hafuman c;
			c.value = dot;
			HafumanTree.push(c);  //传入小根堆
		}
		while (!HafumanTree.empty()) {
			a = HafumanTree.top().value;
			HafumanTree.pop();
			if (HafumanTree.empty()) break;
			b = HafumanTree.top().value;
			HafumanTree.pop();
			hafuman c;
			c.value = a + b;
			HafumanTree.push(c);
			res = res + a + b;


		}
		cout << res << endl;

	}

}

全部评论

相关推荐

06-02 15:53
阳光学院 Java
点赞 评论 收藏
分享
05-23 20:31
已编辑
武汉大学 Java
内向的柠檬精在研究求...:注意把武大标粗标大 本地你俩不是乱杀
实习进度记录
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-09 12:02
ssob上原来真有BOSS啊
硫蛋蛋:这种也是打工的,只不是是给写字楼房东打工
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务