POJ 3253-Fence Repair Fence Repair Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 27581 Accepted: 8976 Description Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs N (1 ≤ N ≤ 20,000) planks of wood, each having some integer length Li (1 ≤ Li ≤ 50,000) units. He then purchases a single long board just long enough to saw into the N planks (i.e., whose length is the sum of the lengths Li). FJ is ignoring the “kerf”, the extra length lost to sawdust when a sawcut is made; you should ignore it, too. FJ sadly realizes that he doesn’t own a saw with which to cut the wood, so he mosies over to Farmer Don’s Farm with this long board and politely asks if he may borrow a saw. Farmer Don, a closet capitalist, doesn’t lend FJ a saw but instead offers to charge Farmer John for each of the N-1 cuts in the plank. The charge to cut a piece of wood is exactly equal to its length. Cutting a plank of length 21 costs 21 cents. Farmer Don then lets Farmer John decide the order and locations to cut the plank. Help Farmer John determine the minimum amount of money he can spend to create the N planks. FJ knows that he can cut the board in various different orders which will result in different charges since the resulting intermediate planks are of different lengths. Input Line 1: One integer N, the number of planks Lines 2..N+1: Each line contains a single integer describing the length of a needed plank Output Line 1: One integer: the minimum amount of money he must spend to make N-1 cuts Sample Input 3 8 5 8 Sample Output 34 Hint He wants to cut a board of length 21 into pieces of lengths 8, 5, and 8. The original board measures 8+5+8=21. The first cut will cost 21, and should be used to cut the board into pieces measuring 13 and 8. The second cut will cost 13, and should be used to cut the 13 into 8 and 5. This would cost 21+13=34. If the 21 was cut into 16 and 5 instead, the second cut would cost 16 for a total of 37 (which is more than 34). Source USACO 2006 November Gold
题目大意是要把一根木棍锯成若干根小棍子，问每锯一次剩余木棍的长度之和最少是多少。 这其实就是哈弗曼树的问题。我们可以想象所有小棍子都锯好了，我们要把他们拼接成原来的长木棍，则每拼接一次的长度就是上一次锯的时候剩余的木棍长度，要使剩余长度之和最小，我们可以每次取最短的两根木棍拼接，这样得到的剩余木棍长度之和自然是最小的。而这就是哈弗曼树。 每次取剩余元素中最小的两个求和，把这两个元素删除，然后插入这个和，如此循环直到最后只剩下一个元素。每次都要取最小的两个元素，本能的想到排序，但是每次都排序效率肯定不高，所以我偷懒的使用了STL中的multiset来解决，multiset的内部实现是红黑树，其插入、查找、删除的效率都是lgn，插入的元素自动排好序了，很不错。所以我们只要不停的插入元素，取头两个元素，求和，删除这两个元素，再插入新元素…直到只剩一个元素。 使用multiset的完整代码如下： [cpp] #include<iostream> #include<set> using namespace std; int main() { int n,tmp; multiset<int> planks; cin>>n; while(n–) { cin>>tmp; planks.insert(tmp); } //int rs=0;//超出最大值 long long rs=0; int curr_sum;//当前两个元素之和 multiset<int>::iterator min_it; while(planks.size()>1) { curr_sum=0; min_it=planks.begin();//最小元素 rs+=*min_it; curr_sum+=*min_it; planks.erase(min_it); min_it=planks.begin();//第二小元素 rs+=*min_it; curr_sum+=*min_it; planks.erase(min_it); planks.insert(curr_sum);//插入新元素 } cout<<rs; return 0; } [/cpp] 本代码提交AC，用时188MS，内存1064K。 需要注意的是，因为1 ≤ N ≤ 20,000且1 ≤ Li ≤ 50,000，最终结果可能超过int的取值范围，需要改为long long才能AC，原因请看这里。 本来到这里本题应该结束了，但是总是用STL里的东西还是有点虚，打算自己实现求2个最小值然后求和插入的过程。基本思路就是将原始数组排序，然后把他们转换为链表，便于后面的插入删除操作；然后取链表的头两个指针求和，然后删除这连个节点，再用插入排序的方式把和插入到链表中。 完整代码如下： [cpp] #include<iostream> #include<vector> #include<list> #include<algorithm> using namespace std; int main() { int n,tmp; vector<int> planks; cin>>n; while(n–) { cin>>tmp; planks.push_back(tmp); } sort(planks.begin(),planks.end());//首先排序 list<int> sorted_planks; vector<int>::iterator it=planks.begin(); while(it!=planks.end())//把数组转换为链表，便于后面的插入删除操作 { sorted_planks.push_back(*it); it++; } long long rs=0; int curr_sum; list<int>::iterator min_it; while(sorted_planks.size()>1) { curr_sum=0; min_it=sorted_planks.begin();//最小元素 rs+=*min_it; curr_sum+=*min_it; sorted_planks.erase(min_it); min_it=sorted_planks.begin();//第二小元素 rs+=*min_it; curr_sum+=*min_it; sorted_planks.erase(min_it); min_it=sorted_planks.begin(); while(min_it!=sorted_planks.end()&&curr_sum>*min_it)//相当于插入排序 { min_it++; } sorted_planks.insert(min_it,curr_sum); } cout<<rs; return 0; } [/cpp] 本代码提交AC，用时1000MS，内存1000K。看来链表的效率还是没有红黑树高啊。 需要注意的是，在对链表插入排序的时候，使用的是如下的代码： [cpp] min_it=sorted_planks.begin(); while(min_it!=sorted_planks.end()&&curr_sum>*min_it)//相当于插入排序 { min_it++; } sorted_planks.insert(min_it,curr_sum); [/cpp] list.insert(it,v)是将v插入到it的前面。需要特别注意的是while循环的条件，因为如果要将6插入到1,2,3,4里面，则如果任由min_it++的话，会超出链表的范围，所以还需要加上min_it!=sorted_planks.end()这个条件，但是把while写成这样： [cpp] while(curr_sum>*min_it&&min_it!=sorted_planks.end())//相当于插入排序 { min_it++; } [/cpp] 也不行，因为如果min_it==sorted_planks.end()，则先执行的是curr_sum>*min_it出错，所以我们需要先判断是否超出了链表的范围，再判断有没有找到正确的位置，利用第一种的while循环条件就可以借助短路原则，即如果min_it!=sorted_planks.end()不满足，则不会执行后面的curr_sum>*min_it，而是while直接跳出。]]>