hdu 2527 Safe Or Unsafeハフマンツリー

ハフマンの木の杭電2527
   2012-5-23 22:09読書(0)
Safe Or Unsafe
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 660    Accepted Submission(s): 220
Problem Description
Javac++一日パソコンの本を読んでいたら、面白いものを見ました!各文字列はいくつかの数字に符号化されて情報を格納することができますが、異なる符号化方式で得られる格納空間は異なります.そして、貯蔵スペースが一定の値より大きい場合は安全ではありません!だからJavac++は文字符号化の最小の空間値を得る方法があるかどうか考えています!本にはハフマン符号化(Huffman Coding)という内容があるので、これは明らかに可能です.1つのアルファベットの重み値は、文字列にアルファベットが現れる頻度に等しい.だからJavac++はあなたに手伝ってもらいたいので、安全な数値と文字列をあげて、この文字列が安全かどうかを判断させますか?
 
Input
複数のcaseが入力され、まず1つの数字nがnグループのデータを表し、その後、各グループのデータが1つの数値m(integer)であり、1つの文字列にスペースがなく、小文字だけで構成されています.
 
Output
文字列の符号化値が所定の値以下である場合yesが出力され、そうでない場合noが出力される.
 
Sample Input

   
   
   
   

    
    
    
    212helloworld66ithinkyoucandoit
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    noyes
   
   
   
   

 
Source
HDU 2008-10 Programming Contest
 
Recommend
gaojie

#include<stdio.h>
#include<string.h>
#define len 100000
struct haha
{
    int start;
    int l[len];
    int weight;
}code[100],cd;
struct xixi
{
    int weight;
    int parent;
    int l_child;
    int r_child;
}tree[100];
int a[300];
int main()
{
    char c[100000];
    int n,k,t,i,j,m,d,m1,m2,x1,x2,pare,child,ans,temp,cnt;
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        n=0;
        scanf("%d",&k);
        getchar();
        gets(c);
        d=strlen(c);
        memset(a,0,sizeof(a));
        for(i=0;i<d;i++)
            a[c[i]]++;
        j=0;
        for(i=90;i<130;i++)
            if(a[i]!=0)
            {
                tree[n].weight=a[i];
                tree[n].l_child=-1;
                tree[n].r_child=-1;
                tree[n].parent=-1;
                n++;                               
            }
            m=2*n-1;
            for(i=n;i<m;i++)
            {
                tree[i].l_child=-1;
                tree[i].r_child=-1;
                tree[i].parent=-1;
                tree[i].weight=0;
            }
            for(i=0;i<n-1;i++)
            {
                m1=m2=1000000000;//    
                x1=x2=0;//         
                for(j=0;j<n+i;j++)
                {
                    if(tree[j].weight<m1&&tree[j].parent==-1)
                    {
                        m2=m1;
                        x2=x1;
                        m1=tree[j].weight;
                        x1=j;
                    }
                    else if(tree[j].weight<m2&&tree[j].parent==-1)
                    {
                        m2=tree[j].weight;
                        x2=j;
                    }
                }
                tree[n+i].weight=tree[x1].weight+tree[x2].weight;
                tree[x1].parent=n+i;
                tree[x2].parent=n+i;
                tree[n+i].l_child=x1;
                tree[n+i].r_child=x2;       
            }
            for(i=0;i<n;i++)
            {
                cd.start=n-1;
                child=i;
                pare=tree[child].parent;
                while(pare!=-1)
                {
                    if(tree[pare].l_child==child)
                        cd.l[cd.start]=0;
                    else cd.l[cd.start]=1;
                    cd.start--;
                    child=pare;
                    pare=tree[child].parent;
                }
                for(j=cd.start+1;j<n;j++)
                {
                    code[i].l[j]=cd.l[j];
                }
                code[i].start=cd.start+1; 
                code[i].weight=tree[i].weight;
                //   printf("code[i]=%d d=%d
",code[i].start,n-code[i].start);
            }
        /*        for(i=0;i<n;i++)
                {
                  ans=ans+(n-code[i].start)*tree[i].weight;//                       
            //      printf("changdu=%d
",n-code[i].start);
                 }
             printf("ans=%d
",ans);
             */
            for(i=0;i<n;i++)
            {
                temp=i;cnt=0;
                while(tree[temp].parent!=-1)
                {
                    /* n 1                      -1
                   cnt=0   ans   0         10 10  dddddddddddddddddddddd    
                          
                    */
                    temp=tree[temp].parent;
                    cnt++;
                }
                ans=ans+cnt*tree[i].weight;
            }
            if(n==1) ans=tree[0].weight;//              n  1         0
              if(ans<=k) printf("yes
");
                 else printf("no
");
    }
    return 0;
}