HDU2527 Safe Or Unsafe（哈夫曼的一道简单题）

如果想进一步了解哈夫曼树的话链接为：http://www.cnblogs.com/jiangjing/archive/2013/01/16/2862828.html

题意:就是给你一个字符串如：12     helloworld统计出其中d:1个，e：1个，h:1个，l：3个，o：2个，r:1个，w：1个,然后用一个数组保存起来a[7]={1,1,1,1,1,2,3};然后就是用哈夫曼树的思想求出新建的非叶子节点的权值之和：sum与12相比较如果sum小于等于12的话就输出yes否则输出no，此案例求出的sum=27；所以输出no。

思路：按照建立哈夫曼树的思路每次求出两个的权值用min1保存最小的，min2保存次小的，然后（min1+min2）加入其中，但是min1和min2需要踢出去，此题我用优先队列做的，就是每次弹出最小的（min1）和次小的(min2)，然后把(min1+min2)压入队列中。

但是有一组很坑爹的测试数据，开始的时候一直错，5 aaaaa 输出的是yes，5 aaaaaa输出的是no

第一种方法（优先队列）代码实现：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
struct node{
    friend bool operator<(node n1,node n2)
    {
        return n1.t>n2.t;
    }
    int t;
};
char a[100001];
int main()
{
    int T,n,i,j,len,b[26],sum,cao;
    node temp;
    while(scanf("%d",&T)!=EOF)
    {
        while(T--)
        {
            sum=0;
            priority_queue<node>Q;
            len=0;
            memset(b,0,sizeof(b));
            scanf("%d",&n);
            getchar();
            scanf("%s",a);
            for(i=0;a[i]!='\0';i++)
                b[a[i]-'a']++;
            for(i=0;i<26;i++)
               if(b[i]!=0)
               {
                   temp.t=b[i];
                   Q.push(temp);
                   len++;
               }
            i=0;
            if(len==1)//坑爹的地方
                sum=Q.top().t;
            else
            {
              while(i<len-1)
              {
                sum+=Q.top().t;//最小的
                cao=Q.top().t;
                Q.pop();
                sum+=Q.top().t;//次小的
                cao+=Q.top().t;
                Q.pop();
                temp.t=cao;
                Q.push(temp);//新形成的加入队列
                i++;
              }
            }
            if(sum<=n)
                printf("yes\n");
            else
                printf("no\n");
        }
    }
    return 0;
}

 第二种方法（建立哈夫曼树的方法，有些步骤可以省的）:

#include<iostream>
#include<cstring>
using namespace std;
struct node{
  int weight;
  int parent,left,right;
};
char a[100001];
int nima(int str[],int size)
{
   int i,lenth=2*size,min1,min2,x,y,sum=0,j;
   struct node *hf;
   hf=(struct node *)malloc(lenth*sizeof(struct node));
   for(i=size;i<lenth;i++)
   {
      hf[i].weight=str[i-size];
      hf[i].parent=hf[i].left=hf[i].right=0;
   }
   for(i=size-1;i>0;i--)
   {
       min1=min2=10000000;x=y=0;
       for(j=i+1;j<lenth;j++)
       {
           if(min1>hf[j].weight&&hf[j].parent==0)
           {
               min2=min1;y=x;
               min1=hf[j].weight;
               x=j;
           }
           else if(min2>hf[j].weight&&hf[j].parent==0)
           {
               y=j;
               min2=hf[j].weight;
           }
       }
       hf[i].weight=min1+min2;
       sum=sum+hf[i].weight;
       hf[i].parent=0;
       if(x>y)
           swap(x,y);
       hf[i].left=y;
       hf[i].right=x;
       hf[x].parent=i;
       hf[y].parent=i;
   }
   return sum;
}
int main()
{
    int T,n,i,j,len,num[26],b[26];
    while(scanf("%d",&T)!=EOF)
    {
        while(T--)
        {
           len=0;
           memset(b,0,sizeof(b));
           scanf("%d",&n);
           getchar();
           scanf("%s",a);
           for(i=0;a[i]!='\0';i++)
               b[a[i]-'a']++;
           for(i=0;i<26;i++)
               if(b[i]!=0)
                   num[len++]=b[i];
               if(len==1)
               {
                   if(num[0]<=n)
                     printf("yes\n");
                   else
                     printf("no\n");
               } 
               else
               {
                   if(nima(num,len)<=n)
                      printf("yes\n");
                   else
                      printf("no\n");
               }
        }
    }
    return 0;
}