POJ3253 哈弗曼树的优先队列解法

发表于 分类于

直接构造优先队列，每次取出最小的两个数相加，直到队列中只有一个数为止，还是用 STL 过的题。

注意 priority_queue 的用法，原型：

1
2
priority_queue<Type> q;
priority_queue<Type, deque<Type>, Comp> q;

其中 Type 是类型，Comp 是比较结构体，比较函数是它的括号重载，比如对 int 型从小到大排序的 Comp 结构体如下：

1
2
3
struct Comp {
  bool operator()(const LL& a, const LL& b) const { return a > b; }
};

这题还要注意使用 long long，不然会越界导致 WA。

我的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

typedef long long LL;
struct Comp {
  bool operator()(const LL& a, const LL& b) const { return a > b; }
};
priority_queue<LL, deque<LL>, Comp> q;

void init() {
  LL n, a;
  while (!q.empty()) q.pop();
  scanf("%lld", &n);
  while (n--) {
    scanf("%lld", &a);
    q.push(a);
  }
}

LL run() {
  LL ret = 0;
  LL a, b;
  while (1) {
    a = q.top();
    q.pop();
    if (q.empty()) break;
    b = q.top();
    q.pop();
    a += b;
    ret += a;
    q.push(a);
  }
  return ret;
}

int main() {
  init();
  printf("%lld\n", run());
  return 0;
}

总结：做题的时候要注意数字的范围，看清到底要用什么类型，是 int 还是 long long。