文章

42

粉丝

0

获赞

35

访问

1.0k

头像
哈夫曼编码 题解:still priority_queue->minHeap but mind the trap!!
P1562
发布于2026年3月11日 19:25
阅读数 15

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

int main()
{
	string s;
	while(cin>>s)
	{
		if(s=="END")
			break;
		int count[130]={0};
		for(int i=0;i<s.size();i++)
			count[s[i]]++;
		priority_queue<int,vector<int>,greater<int>> minHeap;
		for(int i=0;i<130;i++)
			if(count[i])
				minHeap.push(count[i]);
		int total=0;
		if (minHeap.size() == 1)
			total = minHeap.top();
		else
		while(minHeap.size()!=1)
		{
			int a=minHeap.top();
			minHeap.pop();
			int b=minHeap.top();
			minHeap.pop();
			int c=a+b;
			total+=c;
			minHeap.push(c);
		}
		float rate=(float)(8*s.size())/(float)total;
		printf("%d %d %.1f\n",8*s.size(),total,rate);
	}
	return 0;
}
	

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发