97全國能力縣賽 3. Huffman 編碼中的編碼效能問題
作法 : 霍夫曼編碼(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;
}