【哈弗曼树】|【哈弗曼树】 WOJ2343 围栏维修
【描述】
农民 John 希望修复围绕农场的一小段围栏。他测量了一下，发现需要N (1 <= N <= 20,000) 根木头，每根都有某一个整数长度 Li (1 <= Li <= 50,000) 单位长度。 他买了一根很长的很长的木头，正好能够锯出他所需要的N根木头。(即它的长度正好等于 Li的总和) FJ 忽略锯口，锯掉的木屑产生的长度损失忽略不计，你也可以忽略它。
FJ 遗憾的发现他自己没有用于切木头的锯子，所以他就带着那根很长的木头来到了农民 Don 的农场，想问他借一个锯子。
农民 Don是一个保守的资本家，他不愿意借锯子给 FJ ，但愿意自己来切这N-1刀，每一次 都向FJ收取费用。每次的收费正好等于你要锯的那根木头的总长度。例如，你要锯一根长度 为21的木头，就花费21分钱。
【【哈弗曼树】|【哈弗曼树】 WOJ2343 围栏维修】农民 Don 然后让农民 John 自己决定每次锯木头的顺序和位置。帮助农民 John 确定锯出 这N根木头的最小总花费。 FJ 知道可以有很多种不同的切割方式，不同的方式可能得到 不同的总花费，这是因为木头在锯的过程中的长度不一。
【输入】
- Line 1: 一个整数 N，表示要锯出的木头数
- Lines 2..N+1: 每行一个整数，表示每根木头的长度。
- Line 1: 一个整数，表示他最少需要多少分钱，锯N-1下，锯出所有需要的木头。
3
8
5
8
【样例输出】[复制]
34
【提示】
输出解释:
原本的木头长度为 8+5+8=21。第一次锯的花费是 21，应该切成两段长度分别是13和8。 第二次花费是13，把长度是13的木头锯成8和5。总花费是21+13=34。但如果先将21锯成 16和5，第二次将花费16，导致总花费达到37 (大于34)。
【思路】倒着贪心。我们最后得到了N个木头。每次当前取出最小的两个合并之后再丢回去。最后合并成一个木头。一定是最优解。正确性大概就是哈弗曼树的最优性证明。具体实现用一个堆维护就行了。注意统计费用开longlong。
本题可以转化为一个哈弗曼树的构造。具体大概就是一个有n个叶子结点的二叉树。每个叶子结点有一个权值，每个叶子结点的贡献就是【叶子结点到根节点的距离】乘上【点权】。现在要让这个总费用最小。如上所述。。。。
#include
using namespace std;
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return (x*(-1));
}
int N;
long long ans=0;
priority_queue Q;
int main(){
scanf("%d",&N);
for(int i=1;
i<=N;
++i) Q.push(read());
while(Q.size()>=2){
int u=Q.top();
Q.pop();
int v=Q.top();
Q.pop();
ans-=u+v;
Q.push(u+v);
}
cout< 推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长