Poj 3253 Fence Repair(水ハフマンの木)

タイトルリンク:
　　 http://poj.org/problem?id=3253
テーマ:
1本の木の棒があって、n節に切る必要があって、各節はすべて固定の長さがあって、1本の長さxの木の棒は2段を結んで、xを必要として、切断する必要がある状態に最小の費用を必要としますか?
問題解決の考え方:
ハフマン数は、各節に必要な木の棒の長さを木の上のノードと見なし、木の棒を切る過程を逆さまにして、nの棒をつなぐようにして、この2つの過程の費用は同じです.ハフマンの性質から、最短の2つの木の棒をつなぎ合わせた後、残りのn-2本の木の棒の中に置いて、2つの最短の接続を選んで、すべての木の根がつながっているまで戻すとokになることがわかります.
コード:

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <cmath>
 7 #include <queue>
 8 using namespace std;
 9 
10 int main ()
11 {
12     priority_queue <int> Q;//    ，       ，           
13     int n;
14     long long sum, num, m;
15     scanf ("%d", &n);
16     while (n --)
17     {
18         scanf ("%d", &m);
19         Q.push(-m);//  
20     }
21     sum = 0;
22     while (Q.size() > 1)//            1
23     {
24         num = 0;
25 
26         num += Q.top();//        
27         Q.pop();
28 
29         num += Q.top();
30         Q.pop();
31 
32         sum += num;//    
33         Q.push(num);//  
34     }
35     printf ("%lld
", -sum);
36     return 0;
37 }