POJFence Repair 哈夫曼树

哈夫曼树，一个很耳熟的数据结构课上的内容。是用来处理编码的，准确的说是能够去压缩编码，本身是一种无损的压缩凡是，就是对于给定的字符做一个统计，然后根据统计构建一个长短不一的映射表，再根据这个映射表来恢复出原来的内容。

这题是有一个长度为固定值得篱笆L，现在要N块木板来维护好这个篱笆，只要用锯子锯N-1次，题目就是给定N个长度，问如何安排使得最终的花费最短。花费是这样算的，要去锯那一段，那么花费就是这一段的长度。所以就有当某一段没有被分离出来时，那么它将连续作用于切割这一段的效果。因此我们希望起到这个连续作用的值越小越好，因此就可以用哈夫曼树来优化了。使用优先队列来写是非常方便的。

代码如下：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN 50000
using namespace std;

int N;

long long sum;

struct Node {
    int x;
    bool operator < (Node temp) const{
        return x > temp.x;
    }
}info;

priority_queue<Node>q;

void deal() {
    int k; 
    Node pos;
    while (q.size()) {
        k = 0;
        if (q.size() >= 2) {
            pos = q.top();
            k += pos.x;
            q.pop();
            pos = q.top();
            k += pos.x;
            q.pop();
            sum += k;
            pos.x = k;
            q.push(pos);
        }else q.pop();
    }
}

int main()
{
    while (scanf("%d", &N) == 1) {
        while (!q.empty()) {
            q.pop();
        }
        sum = 0;
        for (int i = 1; i <= N; ++i) {
            scanf("%d", &info.x);
            q.push(info);
        }
        deal();
        cout << sum << endl;
    }
    return 0;
}