wordpress 插件游戏关键词优化排名第一

 

题目：http://poj.org/problem?id=1521

题目大意：给定字符串，求哈夫曼编码长和它与等长编码的比值

做这道题目的时候wrang了好几次，但是，

经过调试之后，我彻底了解了哈夫曼树的过程

说来相当有价值了。在下面我也会分享出来的。

#include <iostream>  
#include "cstdio"
#include "string"
#include "cstring"
#include <queue>  
using namespace std;  
struct Num
{int number;bool operator<(const Num &a) const{return number>a.number;}
}tmp;
int main()
{   string s; char c;int numberofchar, i, j, a, b;while(1){priority_queue<Num> que; cin>>s;if(s=="END")break;sort(s.begin(), s.end());c = s[0];numberofchar = 0;for(i=0; i<s.length(); i++){if(s[i]==c)numberofchar++;else{tmp.number = numberofchar;que.push(tmp);c = s[i];numberofchar = 1;}}tmp.number = numberofchar;que.push(tmp);  //细节1：这个地方可不能忘了呀，不然，毫无疑问的wrong answerint oldlen = s.length()*8;int newlen = 0;if(que.size()==1)  //细节2：这个地方也不能忘了，不然，程序会莫名其妙的出错，自然也是wrong answernewlen = que.top().number;while(que.size()>1){a = que.top().number; que.pop();b = que.top().number; que.pop();tmp.number = a+b;newlen += tmp.number;que.push(tmp);}cout<<oldlen<<" "<<newlen<<" ";printf("%.1f\n", (float)oldlen/newlen);}return 0;  
}