锐客网

  1. 首页 > it技术 > >

Tree|【树的算法】之求分割木板最小开销



#include #include using namespace std; /** * 原题: * 现需要将一块木板切成N块，每次切断木板时需要的开销为当前木板的长度。 * 例如要将长度为21的木板切成5/8/8三块木板，长21的木板切成13和8时,开销 * 为21，然后再将长度13的木板切成5和8时，开销为13，于是开销合计是21+13=34。 * 现求:按题目要求将木板切割完后最小的开销是多少 */ #define N 3 static int L[N] = {5,8,8}; /** * 思路: * 逆向求解，即求将N块木板合成一块所需要的最小开销 * 将长度为5和8的木板合成长度13的木板,，开销为13，然后将长度13的木板与长度8的木板 * 进行合成长度为21的木板，开销为21。合计开销为34。 * 显然，每次将最小的两块木板合成时的消耗都是最小的，因此此题可用贪心算法求解 * 下面用优先队列实现贪心算法，时间复杂度为O(NlogN) */ int solve(){ int min = 0; //最小开销 //声明一个从小到大取出数值的优先队列 priority_queue, greater> que; for (int i = 0; i < N; ++i) { que.push(L[i]); } int l1, l2; //不断选取最短的两块木板进行合成,合到只剩1块为止 while (que.size() > 1){ l1 = que.top(); que.pop(); l2 = que.top(); que.pop(); min += l1+l2; que.push(l1 + l2); } return min; }int main() { std::cout << solve() << std::endl; return 0; }



运行结果:

34




【Tree|【树的算法】之求分割木板最小开销】

    推荐阅读


    上一篇：modbus4j,rtu,ascii,tcp/ip传输模式

    下一篇：［|［ Day3 荆九洲 ］财富自由之路读书笔记之二