摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : 霍夫曼編碼(Greedy)

在這裡使用陣列做以及插入排序(不會指標)

/***************************************************************/

#include<stdlib.h>
#include<stdio.h>
double data[401],SUM;
char ch[201][200];
int  xy[500][2]={0},top,used[500]={0};
void DFS(int now,int L)
{
   int a;
   if(used[now]==0)  {SUM+=L*data[now];return;}
   for(a=0;a<2;a++)
      DFS(xy[now][a],L+1);
}
main()
{ 
  int N;
  while(scanf("%d",&N)==1)
       {
         int a,b,c;
         for(a=0;a<N;a++)
            scanf("%s %lf",ch[a],&data[a]);
         for(a=0;a<N;a++)
            {
              c=a;
              for(b=a+1;b<N;b++)
                 if(data[c]>data[b]) c=b;
              double temp;
              temp=data[a];
              data[a]=data[c];
              data[c]=temp;
            }
          top=N; 
          for(a=1;a<top;a+=2)
             {
                xy[top][0]=a,xy[top][1]=a-1;
                data[top]=data[a]+data[a-1];
                used[top]=1;
                top++;
                    for(b=top-1;b>a+1;b--)
                       if(data[b]<data[b-1])
                         {
                            double t;
                            t=data[b];
                            data[b]=data[b-1];
                            data[b-1]=t;
                            xy[b][0]^=xy[b-1][0]^=xy[b][0]^=xy[b-1][0];
                            xy[b][1]^=xy[b-1][1]^=xy[b][1]^=xy[b-1][1];
                            used[b-1]^=used[b]^=used[b-1]^=used[b];
                         }
                       else break;
             }
         /* for(a=0;a<top;a++)
             {
             printf("%lf  ",data[a]);
                if(used[a]==1) printf("%d %d",xy[a][0],xy[a][1]);
                printf("\n");
             }*/
           SUM=0;
           DFS(top-1,0);
           printf("%.2lf\n",SUM);
           for(a=0;a<top;a++)  used[a]=0;
       }
  return 0;
}