题目链接：3253 -- Fence Repair
http://poj.org/problem?id=3253
大致题意：
有一个农夫要把一个木板钜成几块给定长度的小木板，每次锯都要收取一定费用，这个费用就是当前锯的这个木版的长度(锯之前的长度）
给定各个要求的小木板的长度，及小木板的个数n，求最小费用。
Sample Input
3 8 5 8
Sample Output
34
思路：
本题可以用逆向思维来考虑，1块木板分成N块，反过来就是N块木板拼合成一块
我们要求总共的拼合开销是多少。那么就可以用到贪心算法
我们每次贪心地选取最短的两块木板，把他们拼合起来，最终得到的就是最小的总开销
代码：
法1：朴素做法，每次拼合之前都遍历一次数组，找出最短和次短的两块木板，O(n^2)复杂度
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iomanip>
#include <cmath>
#include <climits>
using namespace std;
int N[20000];
int main(){
long long ans = 0; //返回值，即总开销，开始为0（注意ans的值可能很大，要用long long）
int n;
cin >> n; //输入目前木板数量
for(int i=0; i<n; i++){
cin >> N[i]; //输入所有木板的长度
}
while(n > 1){
//当前剩下的木板数量大于1的时候，说明还需要拼合
int m1 = 0, m2 = 1; //两个下标，分别用来存储最短的木板和次短的木板的下标
if(N[m1] > N[m2]) swap(m1, m2); //开始时要保证m1对应的木板更短
for(int i=2; i<n; i++){
//遍历剩下的木板，找出最短的和次短的木板的下标
if(N[i] < N[m1]){ //如果i对应木板比m1和m2都短
m2 = m1;
m1 = i;
}
else if(N[i] < N[m2]){ //如果i对应木板长度在m1和m2之间
m2 = i;
}
}
//然后计算出最短两块木板拼合得到的木板长度，ans要加上这个长度
int tmp = N[m1] + N[m2];
ans += tmp;
//遍历完之后，要加入新拼合成的木板，去掉旧的两块短木板，然后木板数量-1
if(m1 == n-1) swap(m1, m2); //m1要用来记录新木板，不能让它放在最后，否则会被抹去
N[m1] = tmp; //m1记录新木板
N[m2] = N[n-1]; //m2记录准备要被删去的木板
n--; //木板数-1
}
cout << ans << endl;
}这种方法不仅时间复杂度不好，而且每次木板数量-1的时候还有一些细节要处理，比较麻烦。
法2：用优先队列来维护最短的块木板，O(n)复杂度（要注意greater<int>是最小堆而非最大堆，我之前经常记错）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <cstring>
#include <vector>
#include <iomanip>
#include <queue>
#include <cmath>
#include <climits>
using namespace std;
/*
需要注意，调用优先队列用到两个头文件，
一个是<queue>，
一个是<functional>（因为要用到greater<int>这个结构体）
*/
priority_queue<int, vector<int>, greater<int> > q;
//这是一个按照升序排列的优先队列（即最小堆），要特别注意，最小堆是greater<int>。
//这里注意格式，greater<int>的小于号和后面那个小于号之间要有空格，否则会CE
int main(){
int n;
cin >> n; //开始时木板数量
int cur; //当前输入的木板长度
long long ans = 0; //返回值，总开销数（数据很大，注意要用long long）
for(int i=0; i<n; i++){
//输入数据
cin >> cur;
q.push(cur);
}
while(n-- > 1){
int t1 = q.top(); q.pop();
int t2 = q.top(); q.pop();
int sum = t1 + t2;
ans += sum;
q.push(sum);
}
cout << ans << endl;
}