待字闺中的每日一题，题目描述如下：
为了修理栅栏，需要将很长的木板锯为N块，长度分别为L1,L2…LN。锯断一块儿木板，需要一定的开销，开销记为木板的长度。例如，长度为21的木板，锯为三块，长度分别为5，8，8。如下按照如下的顺序据断：
首先锯断21为13和8两块儿，开销为21 然后锯断13为8和5两块儿，开销为13 总的开销为34。但也可以按照如下的顺序：
首先锯断21为16和5两块儿，开销为21 然后锯断16为8和8两块儿，开销为16 总的开销为37。比34要大。
问题是，给定N，以及每一块儿的长度。如何保证最小的开销。尽量采用高效的方法。
需要将木板锯成N块，那么一定需要锯N-1次，这个数字是固定的了。然后的问题是，如何让每次锯的代价都最小，并且第一次锯的代价可能是木板的长度，这个也是一定的。很显然，这是一棵树的过程。我们逆过来看，从树叶到树根，锯木板的开销则是所有非叶子节点之和。并且非叶子节点的个数也是确定了的N-1,那么我们需要每次都木板中选取最短的两根构成新的节点，直到树根。以上面的例子举例：长度21，锯成，5，8，8。那么5，8，8构成叶子节点，首先选取最小的两个点，5和8，构成了13，8，然后这两个过程21。
因为每次都是选取的最小两个点，不管怎样锯，选取的次数一样多，所以最后代价是最小的。这个过程和构造哈夫曼树的过程一样，哈夫曼树也是解决这样的问题，保证编码和解码代价最小。
#include<iostream>
#include<iterator>
#include<set>
using namespace std;
template<typename T>
void printset(const multiset<T>& dataset){
cout << "************output the set**********" << endl;
copy(dataset.begin(),dataset.end(),ostream_iterator<T,char>(cout," "));
cout << endl;
}
bool check(int len, int* blocks, int num){
if(len < 0 || blocks == NULL || num < 0)
return false;
int i = 0,record = 0;
for(i = 0; i < num; i++){
record += blocks[i];
}
return record == len ? true: false;
}
int fenceProblem(int len, int* blocks, int num){
if(check(len,blocks,num) == false){
cout << "please check the number!" << endl;
return -1;
}
multiset<int> blockset;
int i = 0;
for(i; i < num; i++)
blockset.insert(blocks[i]);
printset(blockset);
int record = 0;
multiset<int>::iterator iter;
int first = 0, second = 0;
while(blockset.size()){
iter = blockset.begin();
first = *iter;
blockset.erase(iter++);
second = 0;
if(iter != blockset.end()){
second = *iter;
blockset.erase(iter++);
blockset.insert(first+second);
}
record += first + second;
}
return record - len;
}
int main(){
int len = 21;
int blocks[] = {3,5,6,7};
//int blocks[] = {8,8,5};
int num = sizeof(blocks) / sizeof(int);
cout << "min:" << fenceProblem(len,blocks,num) << endl;
return 0;
}