这道题是哈弗曼树+贪心；
哈夫曼树：
哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
科普就到这了。如果不是很清楚哈弗曼树的话建议自行百度。因为有些好的解答不能转载的原因就不贴链接了。
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
char a[100005];
int num[55];
int cmp(int a,int b)
{return a>b;
}
//排序,从大到小；
int main(int argc, char *argv[])
{int n;int i,j;double wan1,wan2;while(~scanf("%s",a)&&strcmp(a,"END")!=0)//开始输入 {wan1=wan2=0;//wan1代表ascll编码，wan2代表haffman编码memset(num,0,sizeof(num));for(i=0;a[i]!=0;i++){if(a[i]<='Z')num[a[i]-'A']++;//统计字符串里的所有字母的总和 elsenum[26]++;//下划线的总和 } sort(num,num+27,cmp);//排序 wan1=8*i;//ascll编码n=27;while(num[n-1]==0)//去掉为数值为零的数组 n--;while(n>1)//开始构造haffman树运算 {int min1=0,min2=1;//用来取哈弗曼树权值最小的两位 if(num[min1]>num[min2]){int t=min1;min1=min2;min2=t;}for(i=2;i<n;i++){if(num[min1]>num[i]){min2=min1;min1=i;}else if(num[min2]>num[i])min2=i; }//排完序后min1和min2会取到最小值 wan2+=num[min1]+num[min2];//取得两个最小的数构成的权值 if(min1==n-1){int t=min1;min1=min2;min2=t;} num[min1]+=num[min2];//新树的权值 1+2=3； num[min2]=num[n-1];n--;}if(wan2)printf("%.lf %.lf %.1lf\n",wan1,wan2,1.0*wan1/wan2);else printf("%.lf %.lf 8.0\n",wan1,wan1/8);} return 0;
}//Start-ZJ//2017/12/12/19:35