Links to the original text: http://www.cnblogs.com/riasky/p/3430865.html
Problem Description
Javac++ saw an interesting thing while reading computer books one day! Each string of characters can be coded into some numbers to store information, but different encoding methods can get different storage space! And when the storage space is larger than a certain value, it is not safe! So Javac++ wonders if there's a way to get the smallest space value for character encoding! Obviously this is possible, because there is this piece of content in the book, Huffman Coding; the weight of a letter equals the frequency at which the letter appears in the string. So Java c++ wants you to help, give you security values and a string of strings, and let you decide whether the string is safe or not?
Input
Input has many groups of cases, first, a number n denotes that there are n groups of data, then each group of data has a numerical m(integer), and a string of strings without spaces only contain lowercase letters!
Output
If the encoding value of the string is less than or equal to the given value, output yes, otherwise output no.
Sample Input
2
12
helloworld
66
ithinkyoucandoit
Sample Output
no
yes
A simple Huffman tree, at first did not understand the meaning of the topic, after someone told me, it was originally just such a simple Huffman tree, the topic is to require all nodes except leaf nodes weights sum, just after the data structure has just learned the Huffman tree, while the iron is hot.
It should be noted that if there is only one character, Huffman tree can not be built, special treatment is needed.
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int L = 1000000+10;
const int inf = 1<<30;
char str[L];
struct kode
{
int num;
char c;
} b[L<<2];
struct node
{
int wei,parent,lson,rson,cover;
char data;
} a[L<<2];
int main()
{
int i,j,sum,t,len,lb;
char ch;
scanf("%d",&t);
while(t--)
{
scanf("%d%s",&sum,str);
len = strlen(str);
sort(str,str+len);
for(i = 0; i<len<<2; i++)
{
a[i].cover = a[i].lson = a[i].rson = a[i].parent = a[i].wei = b[i].num = 0;
a[i].data = b[i].c = '\0';
}
lb = 0;
b[lb].num = 1;
b[lb].c = ch = str[0];
for(i = 1; i<len; i++)
{
if(str[i] == ch)
b[lb].num++;
else
{
lb++;
ch = str[i];
b[lb].c = ch;
b[lb].num = 1;
}
}
if(lb == 0)//There is only one type of character, direct comparison
{
if(b[lb].num<=sum)
printf("yes\n");
else
printf("no\n");
continue;
}
lb++;
int m = lb*2-1;
for(i = 0; i<lb; i++)
{
a[i].data = b[i].c;
a[i].wei = b[i].num;
}
for(i = 0; i<lb; i++)//Establishment of Huffman Tree
{
int m1 = inf,m2 = inf;
int x = 0,y = 0;
for(j = 0; j<lb+i; j++)
{
if(a[j].wei<m1 && !a[j].cover)
{
m2 = m1;
m1 = a[j].wei;
y = x;
x = j;
}
else if(a[j].wei<m2 && !a[j].cover)
{
m2 = a[j].wei;
y = j;
}
}
a[x].parent = lb+i;
a[y].parent = lb+i;
a[lb+i].lson = x;
a[lb+i].rson = y;
a[lb+i].wei = a[x].wei+a[y].wei;
a[x].cover = a[y].cover = 1;
}
int ans = 0;
for(i = lb; i<2*lb-1; i++)//Find the weights of all nodes except leaf nodes
ans+=a[i].wei;
if(ans<=sum)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
Reprinted at: https://www.cnblogs.com/riasky/p/3430865.html