题解：如图，哈夫曼编码，不断选取规模最小的两个连接，如样例AAAAABCD，A规模为5，B规模为1，C规模为1，D规模为1，那么A取0，BCD为10,110,111时编码长度最短，那么就是C与D先合并，如图中1,2节点，变为规模为2的点，然后与B(3)相连，最后和A(4)连接。其实题目不需要建立哈夫曼树，只要运用其原理即可，就和合并果子是一样的。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 |
#include <cstdio> #include <cstring> #include <queue> using
namespace std; char
line[10000]; int hash[27],len; int main(){ while(scanf("%s",line)){ if(strcmp(line,"END")==0)break; memset(hash,0,sizeof
hash); len=strlen(line); for(int
i=0;i<len;i++){ if(line[i]==‘_‘)hash[0]++; else
hash[line[i]-‘A‘+1]++; } int
flag=0; for(int
i=0;i<27;i++){ if(hash[i]==len){ printf("%d %d 8.0\n",len*8,len); flag=1; break; } } if(flag)continue; priority_queue<int,vector,greater > q; int
ans=0,a,b; for(int
i=0;i<27;i++)if(hash[i]!=0)q.push(hash[i]); while(1){ int
a=q.top();q.pop(); if(q.empty())break; int
b=q.top();q.pop(); ans+=a+b; q.push(a+b); } printf("%d %d %.1lf\n",len*8,ans,len*8.0/ans); } return
0; } |
原文：http://www.cnblogs.com/forever97/p/3562115.html