Safe Or Unsafe

  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        else120          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          else134             cout<<"no"<<endl;135      }136      return 0;137 }