/* Safe Or Unsafe Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1816 Accepted Submission(s): 736 Problem Description Javac++ 一天在看计算机的书籍的时候，看到了一个有趣的东西！每一串字符都可以被编码成一些数字来储存信息，但是不同的编码方式得到的储存空间是不一样的！并且当储存空间大于一定的值的时候是不安全的！所以Javac++ 就想是否有一种方式是可以得到字符编码最小的空间值！显然这是可以的，因为书上有这一块内容--哈夫曼编码(Huffman Coding)；一个字母的权值等于该字母在字符串中出现的频率。所以Javac++ 想让你帮忙，给你安全数值和一串字符串，并让你判断这个字符串是否是安全的？ Input 输入有多组case，首先是一个数字n表示有n组数据，然后每一组数据是有一个数值m(integer)，和一串字符串没有空格只有包含小写字母组成！ Output 如果字符串的编码值小于等于给定的值则输出yes，否则输出no。 Sample Input 2 12 helloworld 66 ithinkyoucandoit Sample Output no yes Source HDU 2008-10 Programming Contest */ #include <iostream> #include<stdio.h> #include <queue> using namespace std; const int strLen=100000; struct Node { int value; Node* left; Node* right; } node[26]; bool operator<(Node a,Node b) { return a.value>b.value; } int WPL(Node* head) { int wpl=0; if(head) { if(head->left&&head->right) wpl+=head->value; wpl+=WPL(head->left)+WPL(head->right); } return wpl; } int main() { int n,m,i,wpl,wpl2; char ch[strLen]; Node*head,*tp,*tp1,*tp2; scanf("%d",&n); while(n--) { head=NULL; wpl=0; scanf("%d",&m); for(i=0; i<26; i++) { node[i].left=NULL; node[i].right=NULL; node[i].value=0; } priority_queue<Node>q; cin>>ch; for(i=0; ch[i]!=' '; i++) { node[ch[i]-'a'].value++; } for(i=0; i<26; i++) if(node[i].value) q.push(node[i]); /* while(!q.empty()) { cout<<(q.top()).value<<endl; q.pop(); } */ while(q.size()>1) { tp1= new Node(); *tp1=q.top(); q.pop(); if(!q.empty()) { tp2= new Node(); *tp2=q.top(); q.pop(); tp= new Node(); tp->left=tp1; tp->right=tp2; tp->value=tp1->value+tp2->value; wpl+=tp->value; q.push(*tp); } } if(!q.empty()) { head= new Node(); *head=q.top(); q.pop(); } if(head&&head->left==NULL&&head->right==NULL) { wpl=head->value; wpl2=head->value; } else wpl2=WPL(head); //printf("%d ",wpl); //printf("%d ",wpl2); if(wpl<=m)//if(wpl2<=m) printf("yes "); else printf("no "); } return 0; }
本题有两个解法，一种是模拟构造haffuman树，边模拟边计算wpl。这种解法其实不需要用结构体，数组就可以，我只不过是为了第二种方法才定义了结构体。
第二种解法就是先构造好haffuman树，然后再通过遍历求得wpl显然第一种更简单。