题目链接:
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;
}
}