文章

232

粉丝

0

获赞

1112

访问

43.4k

头像
哈夫曼编码 题解:
P1562
发布于2026年3月14日 18:28
阅读数 122

#include<iostream>
#include<unordered_map>
#include<queue>
using namespace std;

string str;

void work()
{
    unordered_map<char,int> m;
    priority_queue<int,vector<int>,greater<int>> q;
    for(int i=0;i<str.size();i++)
    m[str[i]]++;
    for(auto p:m)
    q.push(p.second);
	int sum=0;
	if(q.size()==1)
	sum=q.top();
	else
	{
		while(q.size()>1)
		{
			int a=q.top();
			q.pop();
			int b=q.top();
			q.pop();
			sum+=(a+b);
			q.push(a+b);
		}
	}
    cout<<sum<<" ";
    double res=8.0*str.size()/sum;
    printf("%.1f",res);
}

int main()
{
    while(cin>>str)
    {
        if(str=="END")
        break;
        cout<<str.size()*8<<" ";
        work();
        puts("");
    }
    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发