文章目录

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1053
题意：给一个字符串，每个字符需要8个字节，问原来需要多少个字节，经过压缩之后要多少个字节，以及压缩比（这压缩比好奇怪啊为什么不是现在的比上原来的啊）

哈夫曼树就是要把权值重的放在离根节点近的地方
看第一个样例：现在ABCD分别出现了5 1 1 1次，也就是说权重为 5 1 1 1 ，我们这个是二叉的哈夫曼树，所以要找有5个叶子节点的二叉树，然后把权值放进去
然后再合并叶子节点的值，所有的非叶子节点的值的和就是最后的答案了

不用优先队列

这是个优化，有些题用优先队列是会被卡的，毕竟插入删除都会有log级的复杂度，比如hdu5884这道题
所以我们先把原来的数先排序，然后从小到大得选，然后合并的数放在一个新的队列里面，注意这个队列就是普通的队列就行了，因为新合并的肯定比原来的大（除了光是叶子节点的合并，不然 叶子节点+父节点肯定>=父节点），所以这样就少了一个log
这道题0ms过的，而优先队列15ms

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
char s[maxn];
map<char,int>Mp;
int a[maxn]; 
queue<int>que;
int main()
{
	cout.setf(ios::fixed);
	while(cin>>(s+1))
	{
		if(s[1]=='E'&&s[2]=='N'&&s[3]=='D')break;
		while(!que.empty())que.pop();
		Mp.clear();
		int ans=0;
		int N=strlen(s+1);
		for(int i=1;i<=N;i++)Mp[s[i]]++;
		int t=0;
		for(auto i:Mp)a[++t]=i.second;
		sort(a+1,a+1+t);		
		int k=2;//k叉哈夫曼树 
		int now=1;
		while(t-now+1+que.size()>=k)
		{
			int tp=0;
			for(int i=1;i<=k;i++)
			{
				if(que.empty() || now<=t&&a[now]<=que.front())tp+=a[now++];	//从原来的数组里面选 
				else if(now>t || !que.empty()&&que.front()<=a[now])			//从新加的队列里面选 
				{
					tp+=que.front();
					que.pop();
				}
			}
			que.push(tp);
			ans+=tp;

		}
		if(ans==0)ans=a[1];//只有一堆 
		cout<<N*8<<" "<<ans<<" "<<setprecision(1)<<1.0*N*8/ans<<endl;
	}
}

优先队列

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
char s[maxn];
map<char,int>Mp;
int a[maxn]; 
priority_queue<int,vector<int>,greater<int> >que;
int main()
{
	cout.setf(ios::fixed);
	while(cin>>(s+1))
	{
		if(s[1]=='E'&&s[2]=='N'&&s[3]=='D')break;
		while(!que.empty())que.pop();
		Mp.clear();
		int N=strlen(s+1);
		for(int i=1;i<=N;i++)Mp[s[i]]++;
		for(auto i:Mp)que.push(i.second);
		int ans=0;
		while(que.size()>1)
		{
			int t1=que.top();
			que.pop();
			int t2=que.top();
			que.pop();
			ans+=t1+t2;
			que.push(t1+t2);
		}
		if(ans==0)ans=que.top();//只有一堆 
		cout<<N*8<<" "<<ans<<" "<<setprecision(1)<<1.0*N*8/ans<<endl;
	}
}