Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
字符的编码方式有多种，除了大家熟悉的ASCII编码，哈夫曼编码(Huffman Coding)也是一种编码方式，它是可变字长编码。该方法完全依据字符出现概率来构造出平均长度最短的编码，称之为最优编码。哈夫曼编码常被用于数据文件压缩中，其压缩率通常在20%～90%之间。你的任务是对从键盘输入的一个字符串求出它的ASCII编码长度和哈夫曼编码长度的比值。
Input
输入数据有多组，每组数据一行，表示要编码的字符串。
Output
对应字符的ASCII编码长度la，huffman编码长度lh和la/lh的值(保留一位小数)，数据之间以空格间隔。
Sample Input
AAAAABCD THE_CAT_IN_THE_HATSample Output
64 13 4.9 144 51 2.8Hint
Source
xam
哈夫曼编码在离散数学里有提及，其原理是
哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。其构造步骤如下：
难点在于哈夫曼二叉树的建立，而哈夫曼编码是以自底向上的方式构造表示最优先前缀码的二叉树，这里需要用到优先队列。用到了STL标准函数库中的优先队列函数：priority_queue<int> qi
此函数是在优先队列中，优先级高的元素优先出队列，STl标准库中默认使用的是小于操作符来确定它们之间的关系。所以当需求是优先级低的元素优先出队列的话直接调用priority_queue<int>qi函数即可。但是如果需求是根据大于操作符来确定之间的优先关系，就需要加上二级参数。即调用：priority_queue<int,vector<int>,greater<int> >qi2;当然这个函数里面的greater<int>的参数部分可以根据需要来进行编写。
本题调用优先队列函数和队列函数集可以写出很简洁的代码。
ASCII码对照表和部分语言运算符优先级点我
AC代码：
#include<bits/stdc++.h>//万能头 using namespace std; int main() { char s[10010]; int b[200]; int al; while(~scanf("%s",s)) { priority_queue<int,vector<int>,greater<int> >q;//调用优先队列函数，因为需要优先输出等级高的元素，所以采用第二种函数。 int n; n=strlen(s);//记录输入字符串的长度 memset(b,0,sizeof(b));//记得清空b数组，b数组的作用是用来根据ASCII码来确定各个字符出现的频率的过渡数组。 al=n*8;//al的长度就是字符长度乘8，因为一个字符占用8个编码长度。一个编码长度就是一个bit，一个字符8bit。 for(int i=0;i<n;i++)//确定各个字符出现的次数 { b[s[i]]++; } for(int i=0;i<150;i++)//ASCII码最高到127，所以不用遍历很高 { if(b[i]!=0) { q.push(b[i]);//出现就进队列 } } int a,b; int c,sum=0; while(!q.empty())//当队列不为空的时候 { a=q.top();//a等于队头元素 q.pop();//队头元素出队列 if(!q.empty())//a元素之后如果队列不空，那么b进行同样的操作 { b=q.top(); q.pop(); c=a+b;//这里直接相加即可 sum=sum+c; q.push(c); } } printf("%d %d %.1lf\n",al,sum,1.0*al/sum); } return 0; }