文章

10

粉丝

165

获赞

7

访问

25.7k

头像
题解:哈弗曼编码
P1562
发布于2022年9月26日 12:41
阅读数 5.7k

 

#include<bits/stdc++.h>
using namespace std;

string str;
int len, num[30];

int bfs() {
	priority_queue<int, vector<int>, greater<int> > q;  // 创建优先队列,从小到大排序
	for(int i = 0; i < 30; i++) {
		if(num[i])	q.push(num[i]);  // 放入每个字母的个数
	}
	int sum = 0;
	if(q.size() == 1)	sum = q.top();  // 如果只有一个字母,直接等于该字母的数量
	while(q.size() > 1) {  // 得到前两个最小的叶子节点,将和放入队列中
		int a = q.top();	q.pop();
		int b = q.top();	q.pop();
		sum += (a + b);	    q.push(a + b);   // 因为ans累加了之前的值,所以传入的是a  + b而非ans;
	}
	return sum;
}

int main() {
	while(cin >> str) {
		memset(num, 0, sizeof num);
		if(str == "END")	break;  // 注意为双引号
		len = str.size();  // 得到string类型的长度
		for(int i = 0; i < len; i++) {
			if(str[i] == '_')	num[26]++;  // 应为'A' - 'A'等于0,从下标0开始,所以'_'就在num[26]
			else	num[str[i] - 'A']++;
		} 
		int res = bfs();
		printf("%d %d %.1lf\n", len * 8, res, len * 8.0 / res);
	}
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发