本文主要是介绍poj3253 FenceRepair，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
大致题意：
有一个农夫要把一个木板钜成几块给定长度的小木板，每次锯都要收取一定费用，这个费用就是当前锯的这个木版的长度
给定各个要求的小木板的长度，及小木板的个数n，求最小费用
提示：
以
3
5 8 5为例：
先从无限长的木板上锯下长度为 21 的木板，花费 21
再从长度为21的木板上锯下长度为5的木板，花费5
再从长度为16的木板上锯下长度为8的木板，花费8
总花费 = 21+5+8 =34
解题思路：
利用Huffman思想，要使总费用最小，那么每次只选取最小长度的两块木板相加，再把这些“和”累加到总费用中即可
本题虽然利用了Huffman思想，但是直接用HuffmanTree做会超时，可以用优先队列做
因为朴素的HuffmanTree思想是：
（1）先把输入的所有元素升序排序，再选取最小的两个元素，把他们的和值累加到总费用
（2）把这两个最小元素出队，他们的和值入队，重新排列所有元素，重复（1），直至队列中元素个数<=1，则累计的费用就是最小费用
HuffmanTree超时的原因是每次都要重新排序，极度浪费时间，即使是用快排。
用STL的优先队列即可，还是很简单的
注意priority_queue与qsort的比较规则的返回值的意义刚好相反
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stdio.h>
using namespace std;
class cmp
{
public:bool operator()(const __int64 a,const __int64 b)const{return a>b;}
};
int main()
{int n;while(scanf("%d",&n)!=EOF){priority_queue<__int64,vector<__int64>,cmp>queue;for(int i=0;i<n;i++){__int64 tmp;scanf("%I64d",&tmp);queue.push(tmp);}__int64 mincost=0;while(queue.size()>1){__int64 a=queue.top();queue.pop();__int64 b=queue.top();queue.pop();mincost+=(a+b);queue.push(a+b);}printf("%I64d",mincost);queue.pop();}return 0;
}
这篇关于poj3253 FenceRepair的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
