Fence Repair poj3253(贪心/哈夫曼树)

Fence Repair poj3253
传送门 http://poj.org/problem?id=3253

利用优先队列构造哈夫曼树。这个结构本身就是求的WPL，但是这个思路来源并不是这个。而是自底向上的贪心思想：每次取两个最小的板子合在一起，那么费用肯定是最低的。合成到最后阶段，就是整个板子。

#include 
#include 
#include 
#include 
#include 
#include 
typedef long double ld;
typedef long long ll;
#define qwe(i,a,b) for(int i=a;i<=b;i++)
#define ewq(i,a,b) for(int i=a;i>=b;i--)
ll rr(){ll x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();return x;}
using namespace std;
const int maxn=2e4+6;

priority_queue,greater > q;
ll sum=0;
int main(int argc, char const *argv[]) {
    ll n=rr();
    qwe(i,1,n){
        ll tmp=rr();
        q.push(tmp);
    }
    while (q.size()>1) {
        ll a=q.top();q.pop();
        ll b=q.top();q.pop();
        sum+=a+b;
        q.push(a+b);
    }
    std::cout << sum << 'n';
    return 0;
}

∑ i = 1 n W i ∗ L i sum_{i=1}^{n}Wi*Li i=1∑n​Wi∗Li

权值越大的叶节点越靠近根节点，权值越小的越远离根节点。权值越大的编码越短，权值越小的哈夫曼编码越长。

总节点个数：叶子节点数为n₀，那么总结点数为2n₀-1(根节点也是节点)。

哈夫曼编码属于前缀编码，不可能出现一个哈夫曼编码是另一个哈夫曼编码的前缀。

1. 先从小到大排序，每个数据都是一个根节点；
2. 取出最小的两个根节点合并成一个二叉树，此二叉树的权值是两节点之和；
3. 把该二叉树放入数列中继续排序；

循环以上步骤，直到数列中只有一个