/*
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=;
struct Node
{
int value;
Node* left;
Node* right;
} node[];
bool operator<(Node a,Node b)
{
return a.value>b.value;
}
int WPL(Node* head)
{
int wpl=;
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=;
scanf("%d",&m);
for(i=; i<; i++)
{
node[i].left=NULL;
node[i].right=NULL;
node[i].value=;
}
priority_queue<Node>q;
cin>>ch;
for(i=; ch[i]!='\0'; i++)
{
node[ch[i]-'a'].value++;
}
for(i=; i<; i++)
if(node[i].value)
q.push(node[i]);
/*
while(!q.empty())
{
cout<<(q.top()).value<<endl;
q.pop();
}
*/
while(q.size()>)
{
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\n",wpl);
//printf("%d\n",wpl2);
if(wpl<=m)//if(wpl2<=m)
printf("yes\n");
else
printf("no\n");
}
return ;
}
本题有两个解法，一种是模拟构造haffuman树，边模拟边计算wpl。这种解法其实不需要用结构体，数组就可以，我只不过是为了第二种方法才定义了结构体。
第二种解法就是先构造好haffuman树，然后再通过遍历求得wpl显然第一种更简单。