ding. The letters “C”, “I’ and “N” only occur once, however, so they will have the longest codes.
There are many possible sets of prefix-free variable-length bit patterns that would yield the optimal encoding, that is, that would allow the text to be encoded in the fewest number of bits. One such optimal encoding is to encode spaces with “00”, “A” with “100”, “C” with “1110”, “E” with “1111”, “H” with “110”, “I” with “1010”, “N” with “1011” and “T” with “01”. The optimal encoding therefore requires only 51 bits compared to the 144 that would be necessary to encode the message with 8-bit ASCII encoding, a compression ratio of 2.8 to 1.
Input The input file will contain a list of text strings, one per line. The text strings will consist only of uppercase alphanumeric characters and underscores (which are used in place of spaces). The end of the input will be signalled by a line containing only the word “END” as the text string. This line should not be processed.
Output For each text string in the input, output the length in bits of the 8-bit ASCII encoding, the length in bits of an optimal prefix-free variable-length encoding, and the compression ratio accurate to one decimal point.
Sample Input
AAAAABCD
THE_CAT_IN_THE_HAT
END
Sample Output
64 13 4.9
144 51 2.8
Source Greater New York 2000
思路：此题不需要编码，只需要求编码的长度而已，直接乱搞。
#include
#include
#include
#include
using namespace std; int num[27]; char s[100005]; struct S{ int val; S(int a){val=a;} bool operator<(const S &p) const { return val>p.val; } }; int main() { int n,i,len,ans,a,b,cnt; while(~scanf("%s",s)) { len=strlen(s); if(len==3 && s[0]=='E' && s[1]=='N' && s[2]=='D') return 0; memset(num,0,sizeof num); for(i=0;i
que; cnt=0; for(i=0;i<27;i++) if(num[i]) { que.push(num[i]); cnt++; } if(cnt==1)//特判 { printf("%d %d %.1f\n",len*8,len,8.0); continue; } ans=0; while(que.size()>1) { a=que.top().val; que.pop(); b=que.top().val; que.pop(); ans+=a+b; que.push(a+b); } printf("%d %d %.1f\n",len*8,ans,(double)len*8/ans); } }