In computer science and information theory, a Huffman code is an optimal PRefix code algorithm.

In this exercise, please use Huffman coding to encode a given data.

You should output the number of bits, denoted asB(T), to encode the data:

B(T)=∑f(c)d_T(c),

wheref(c) is the frequency of characterc, and d_T(c) is be the depth of characterc's leaf in the treeT.

The first line is the number of characters n.

The following n lines, each line gives the character c and its frequencyf(c).

 Output a single number B(T).

50 51 42 63 24 3Sample Output
45Hint0: 011: 002: 113: 1004: 101這道題是哈夫曼編碼，主要是優(yōu)先隊列沒用好，數(shù)據(jù)類型的指針變量應(yīng)該這么傳參才能小根堆，如果是普通變量可以直接在結(jié)構(gòu)體里重載 < 即可，其余沒什么
#include <iostream>#include <queue>#include <map>using namespace std;struct huffman{    char c;    int num;};struct tree{    huffman h;    tree* left;    tree* right;    }; struct cmp{	bool Operator() (tree const*a, tree const*b){		return a->h.num > b->h.num;	}};//小根堆比較 map <char,int> mm;void deal(tree* t,int n){    if(t->left==NULL&&t->right==NULL){        mm[t->h.c]=n;    }    else {        deal(t->left,n+1);        deal(t->right,n+1);    }}//計算樹的深度，用于計算字符長度 int main(){    int n;    cin >> n;    priority_queue <tree*, vector<tree*>, cmp> pq;    huffman hu[1001];    for(int i=0; i < n; ++i){        cin >> hu[i].c >> hu[i].num;        tree *tmp=new tree;        tmp->h=hu[i];        tmp->left=NULL;        tmp->right=NULL;        pq.push(tmp);    }//將字符存進優(yōu)先隊列     /*tree* t=pq.top();	cout << t->h.c << endl; */    while(pq.size() > 1){        tree* t1=pq.top();        //cout << t1->h.c << "   "<<t1->h.num << endl;        pq.pop();        tree* t2=pq.top();        //cout << t2->h.c << "   "<< t2->h.num << endl;        pq.pop();        tree *tmp=new tree;        tmp->h.c='.';        tmp->h.num=t1->h.num+t2->h.num;        tmp->left=t1;        tmp->right=t2;        pq.push(tmp);        //cout << endl;    }//建立哈夫曼編碼樹     tree* res=pq.top();    //cout << res->h.num << endl;    deal(res,0);    int resu=0;	for(int i=0; i < n; ++i){		//cout << hu[i].num << "   "  << mm[hu[i].c] << endl;		resu+=(hu[i].num*(mm[hu[i].c]));		}	cout << resu << endl;}