[HDOJ5350]MZL's munhaff function

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5350

智商题…求最小哈夫曼树的编码。取数据中最小的两个数，相加并加到总和中，将相加后的和作为一个节点。

用到优先队列。

比如case2，最小哈夫曼树是这样的。

            104
          /     
         50     54
        /     / 
      25  25  28  26
      /
     1 24

将所有非叶节点的值相加即可。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 priority_queue<int, vector<int>, greater<int> > pq;
23 
24 int main() {
25     // freopen("in", "r", stdin);
26     int T, n;
27     int tmp;
28     scanf("%d", &T);
29     while(T--) {
30         while(!pq.empty()) {
31             pq.pop();
32         }
33         scanf("%d", &n);
34         for(int i = 0; i < n; i++) {
35             scanf("%d", &tmp);
36             pq.push(tmp);
37         }
38         long long ans = 0;
39         int a, b;
40         while(n-- > 1) {            
41             a = pq.top();
42             pq.pop();
43             b = pq.top();
44             pq.pop();
45             tmp = a + b;
46             pq.push(tmp);
47             ans += tmp;
48         }
49         printf("%I64d
", ans);
50     }
51 }

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 priority_queue<int, vector<int>, greater<int> > pq;
23 
24 int main() {
25     // freopen("in", "r", stdin);
26     int T, n;
27     int tmp;
28     scanf("%d", &T);
29     while(T--) {
30         while(!pq.empty()) {
31             pq.pop();
32         }
33         scanf("%d", &n);
34         for(int i = 0; i < n; i++) {
35             scanf("%d", &tmp);
36             pq.push(tmp);
37         }
38         long long ans = 0;
39         int a, b;
40         while(n-- > 1) {            
41             a = pq.top();
42             pq.pop();
43             b = pq.top();
44             pq.pop();
45             tmp = a + b;
46             pq.push(tmp);
47             ans += tmp;
48         }
49         printf("%I64d
", ans);
50     }
51 }