HDU-2527 Safe Or Unsafe

http://acm.hdu.edu.cn/showproblem.php?pid=2527
하프 만 트 리, 하프 만 인 코딩, wpl 값 구하 기.
Safe Or Unsafe
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1511    Accepted Submission(s): 594
Problem Description
자바 c + + 하루 컴퓨터 책 을 보다 가 재 미 있 는 것 을 봤 어 요!모든 문 자 는 숫자 로 인 코딩 되 어 정 보 를 저장 할 수 있 지만 서로 다른 인 코딩 방식 으로 얻 은 저장 공간 은 다르다!그리고 저장 공간 이 일정한 값 보다 클 때 안전 하지 않 습 니 다!그래서 자바 c + 는 문자 인 코딩 의 최소 공간 값 을 얻 을 수 있 는 방법 이 있 는 지 생각 합 니 다!분명히 이것 은 가능 하 다. 왜냐하면 책 에 이런 내용 이 있 기 때문이다. 하 프 만 코드 (Huffman Coding).한 자모의 가중치 는 문자열 에 나타 나 는 주파수 와 같다.그래서 자바 c + 는 보안 수치 와 문자열 을 주 고 이 문자열 이 안전 한 지 판단 하 는 데 도움 을 주 고 싶 습 니 다.
 
Input
여러 개의 케이스 를 입력 하 십시오. 먼저 하나의 숫자 n 은 n 개의 데이터 가 있 음 을 표시 합 니 다. 그 다음 에 각 그룹의 데 이 터 는 하나의 수치 m (integer) 가 있 고 문자열 과 빈 칸 이 없 으 며 소문 자 만 포함 되 어 있 습 니 다!
 
Output
문자열 의 인 코딩 값 이 주어진 값 보다 작 으 면 yes 를 출력 합 니 다. 그렇지 않 으 면 no 를 출력 합 니 다.
 
Sample Input
2
12
helloworld
66
ithinkyoucandoit
 
Sample Output
no
yes

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 using namespace std;
  5 struct node
  6 {
  7     char ch;//   
  8     int weight;//  
  9     int parent;//    
 10     int lchild,rchild;//    
 11 }ht[20020];
 12 struct Hcode
 13 {
 14     char cd[10010];//  01      。
 15     int start;//     。
 16 }hcd[10010];
 17 void creat(node ht[],char *c,int *w,int n)//     。
 18 {
 19      int i,s1,s2,k,min1,min2;
 20     for(i=1;i<=n;i++)//       
 21     {
 22         ht[i].ch=c[i-1];//  。
 23         ht[i].weight=w[i-1];//  
 24         ht[i].parent=ht[i].lchild=ht[i].rchild=0;//   0.
 25     }
 26    for(;i<2*n;i++)//       2*n-1 。
 27     {
 28       ht[i].parent=0;
 29       ht[i].lchild=0;
 30       ht[i].rchild=0;
 31     }
 32    for(i=n+1;i<2*n;i++)
 33     {
 34         min1 = min2 = 9999999;
 35         for(k=1;k<=i-1;k++)//      2   。
 36              if(ht[k].parent == 0)
 37              {
 38                  if(ht[k].weight<min1)
 39                  {
 40                       min2 = min1;
 41                       s2= s1;
 42                       min1= ht[k].weight;
 43                       s1= k;
 44                   }
 45                   else if(ht[k].weight<min2)
 46                   {
 47                       min2 = ht[k].weight;
 48                       s2 = k;
 49                   }
 50             }
 51         
 52          ht[s1].parent=i;//    。
 53         ht[s2].parent=i;
 54         ht[i].lchild=s1;
 55         ht[i].rchild=s2;
 56         ht[i].weight=ht[s1].weight+ht[s2].weight;
 57      
 58     }
 59   
 60 }
 61 void creatHcode(node ht[],Hcode hcd[],int n)//     。
 62 {
 63     int i,f,c;
 64     Hcode hc;
 65     for(i=1;i<=n;i++)
 66     {
 67         hc.start=n;
 68         c=i;
 69         f=ht[i].parent;
 70         while(f!=0)
 71         {
 72             if(ht[f].lchild==c)
 73                 hc.cd[hc.start--]='0';
 74             else
 75                hc.cd[hc.start--]='1';
 76             c=f;
 77             f=ht[f].parent;
 78         }
 79         hc.start++;
 80         hcd[i]=hc;
 81     }
 82 }
 83 int main()
 84 {
 85   int T,m,i,r,j;
 86    int w[200];
 87   char str[200],c[200];
 88   scanf("%d",&T);
 89   while(T--)
 90   {
 91      memset(w,0,sizeof(w));
 92       scanf("%d",&m);
 93       getchar();
 94       scanf("%s",str);
 95      int len=strlen(str);
 96            r=0;
 97            c[r++]=str[0];
 98            w[0]=1;
 99       for(i=1;i<len;i++)
100       {
101          for(j=0;j<r;j++)
102             {
103                  if(c[j]==str[i])
104                    {
105                      w[j]=w[j]+1;
106                      break;
107                    }
108             }
109             if(j==r)
110                {  w[r]=1;
111                    c[r++]=str[i];
112                }
113        }
114      c[r]='\0';
115      if(r==1)
116      {
117       if(w[0]<=m)
118          cout<<"yes"<<endl;
119        else
120          cout<<"no"<<endl;
121         continue;
122      }
123      creat(ht,c,w,r);
124      creatHcode(ht,hcd,r);
125      int wpl=0;
126        for(i=1;i<=r;i++)
127        {
128           wpl+=(r-hcd[i].start+1)*ht[i].weight;
129         
130        }
131      if(wpl<=m)
132             cout<<"yes"<<endl;
133          else
134             cout<<"no"<<endl;
135      }
136      return 0;
137 }