PKU 1521 Entropy
http://poj.org/problem?id=1521
8bitで表されているASCI文字を入力された文字列が短くなるような可変長のビット列に置き換えて、その長さと、元の長さとの比率を求めろというような問題。
ハフマン圧縮とかそのへんの問題に似ている気がします。
文字種1個を考慮し忘れて1WA
string in; void solve(){ map<char,int> app; FOR(it,in)app[*it]++; priority_queue<int> q; FOR(it,app) q.push(-it->S); int ans=0; while(SZ(q)>1){ int a=q.top();q.pop(); int b=q.top();q.pop(); ans+=-a; ans+=-b; q.push(a+b); } if(SZ(app)==1) ans=SZ(in); printf("%d %d %.1f\n",SZ(in)*8,ans,SZ(in)*8.0/ans); } main(){ while(cin>>in,in!="END")solve(); }