九度oj 题目1172：哈夫曼树

题目描述：: 哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。

输入：: 输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。

输出：: 输出权值。

样例输入：

5  
1 2 2 5 9

样例输出：

37

权值为层数，从0开始，一开始本来想用数组来构造哈夫曼树，代码如下：

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <string>
 5 #include <algorithm>
 6  
 7 #define MAX 1009
 8 #define HMAX 2009
 9  
10 struct Haff
11 {
12     int level;
13     int key;
14     bool isLeaf;
15 };
16 Haff haff[MAX];
17  
18 int cmp(const void* a, const void *b) {
19     Haff at = *(Haff *)a;
20     Haff bt = *(Haff *)b;
21     if(at.key != bt.key)
22         return at.key - bt.key;
23     else if(at.isLeaf == bt.isLeaf) {
24         return 0;
25     }
26     else {
27         if(at.isLeaf == true) {
28             return 1;
29         }
30         else {
31             return -1;
32         }
33     }
34 }
35  
36 int max(int a, int b) {
37     return a > b ? a: b;
38 }
39 int main(int argc, char const *argv[])
40 {
41     int n;
42     while(scanf("%d",&n) != EOF) {
43         for(int i = 0; i < n; i++) {
44             scanf("%d",&haff[i].key);
45             haff[i].level = 1;
46             haff[i].isLeaf = true;
47         }
48         int ptr = 0;
49         int count = n;
50         int cen;
51         int N = 2 * n - 1;
52         while(ptr < N - 2) {
53             qsort(&haff[ptr],count-ptr, sizeof(Haff), cmp);
54              
55             int pj = ptr + 1;
56             cen = max(haff[ptr].level, haff[pj].level);
57             haff[ptr].level = cen;
58             haff[pj].level = cen;
59             haff[count].key = haff[ptr].key + haff[pj].key;
60             haff[count].level = cen + 1;
61             haff[count].isLeaf = false;
62             count++;
63             ptr = ptr + 2;
64         }
65  
66         int sum = 0;
67         cen = haff[N-1].level;
68  
69         /*for(int i = 0; i  < count; i++) {
70             printf("%d %d	",haff[i].key, haff[i].level);
71         }
72         printf("
");*/
73         for(int i = 0; i  < count; i++) {
74             if(haff[i].isLeaf == true) {
75                 sum = sum + (cen - haff[i].level) * haff[i].key;
76             }
77         }
78         printf("%d
",sum);
79     }
80     return 0;
81 }
82

但这样做，level的值会出现错误。

后来发现去计算答案根本不需要建树，代码如下：

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <string>
 5 #include <algorithm>
 6 
 7 #define MAX 1009
 8 
 9 int haff[MAX];
10 
11 int cmp(const void* a, const void *b) {
12     int at = *(int *)a;
13     int bt = *(int *)b;
14     return at - bt;
15     
16 }
17 
18 int max(int a, int b) {
19     return a > b ? a: b;
20 }
21 int main(int argc, char const *argv[])
22 {
23     int n;
24     while(scanf("%d",&n) != EOF) {
25         for(int i = 0; i < n; i++) {
26             scanf("%d",&haff[i]);
27         }
28         int ptr = 0;
29         int count = n;
30         int N = 2 * n - 1;
31         int sum = 0;
32         while(ptr < N - 2) {
33             qsort(&haff[ptr],count-ptr, sizeof(int), cmp);
34             
35             int pj = ptr + 1;
36             haff[count] = haff[ptr] + haff[pj];
37             sum = sum + haff[count];
38             count++;
39             ptr = ptr + 2;
40         }
41         printf("%d
",sum);
42     }
43     return 0;
44 }