VIJOS1097 - [NOIP2004]合并果子

2016/11/17

裸的 Huffman 树。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <iostream>
#include <queue>
#define _R register
using namespace std;
priority_queue<int, vector<int>, greater<int>> Q;

int main() {
    _R int M; cin >> M;
    _R int t;
    while(M--) { cin >> t; Q.push(t); }
    _R int ans = 0;
    while(Q.size() > 1) { t = Q.top(); Q.pop(); t += Q.top(); Q.pop(); ans += t; Q.push(t); }
    cout << ans << endl;
}