计算哈夫曼树的带权路径长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
    return *(int*)a-*(int *)b;
}
int main()
{
    int n,W[1001];
    while(scanf("%d",&n)!=EOF) //n为权值个数
    {
        for(int i=1;i<=n;i++)	//n个权值
            scanf("%d",&W[i]);
        int Result=0;
        for(int i=2;i<=n;i++){
           qsort(W+i-1,n-i+2,sizeof(W[0]),cmp); //C语言快速排序函数
           Result+=W[i]+W[i-1];
           W[i]=W[i]+W[i-1];
            
        }
        printf("%d\n",Result);
    }
    return 0;
}