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

79愛的鼓勵 1訂閱站台

作法 : 霍夫曼編碼(Greedy)

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

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

#include<stdlib.h>
#include<stdio.h>
int data[100001],SUM;
int  xy[100000][2]={0},top,used[100000]={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("%d",&data[a]);
         for(a=0;a<N;a++)
            {
              c=a;
              for(b=a+1;b<N;b++)
                 if(data[c]>data[b]) c=b;
              int temp;
              temp=data[a];
              data[a]=data[c];
              data[c]=temp;
            }
          top=N; 
          for(a=1;a<top;a+=2)
             {
                int tt=data[a]+data[a-1];
                    for(b=top-1;b>a;b--)
                       if(tt<data[b])
                        data[b+1]=data[b],xy[b+1][0]=xy[b][0],xy[b+1][1]=xy[b][1],used[b+1]=used[b];
                       else break;               
                data[b+1]=tt;
                used[b+1]=1;
                xy[b+1][0]=a,xy[b+1][1]=a-1;
                top++;
             }
         /* 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("%d\n",SUM);
           for(a=0;a<top;a++)  used[a]=0;
       }
  return 0;
}