篱笆修理(Fence Repair) 代码(C)
本文地址: http://blog.csdn.net/caroline_wendy
题目: 把一块木板切成N块, 每次切两块, 分割的开销是木板长度, 求将木板分割完的最小开销.
即霍夫曼编码(Huffman).
贪心算法, 相似二叉树型结构, 最短板和次短板是兄弟结点, 选取两个最小木板, 最后进行分割, 合并两个最小木板, 依次递推.
代码:
/** main.cpp** Created on: 2014.7.17* Author: spike*//*eclipse cdt, gcc 4.8.1*/#include <stdio.h>
#include <limits.h>#include <utility>
#include <queue>
#include <algorithm>using namespace std;class Program {typedef long long ll;static const int MAX_N = 10000;int N=5, L[MAX_N]={1,2,3,4,5};public:void solve() {ll ans = 0;while (N>1) {int mii1 = 0, mii2 = 1;if (L[mii1]>L[mii2]) swap(mii1, mii2);for (int i=2; i<N; ++i) {if (L[i]<L[mii1]) {mii2 = mii1;mii1 = i;} else if (L[i]<L[mii2]) {mii2 = i;}}int t = L[mii1]+L[mii2];ans += t;if (mii1 == N-1) swap(mii1, mii2);L[mii1] = t;L[mii2] = L[N-1];N--;}printf("result = %lld\n", ans);}
};int main(void)
{Program P;P.solve();return 0;
}输出:
result = 33
