Fence Repair 栅栏分割
##Rence Repair
题目：
农夫约翰为了修理栅栏，要将一块很长的木板分割成N块。准备切成的木板的长度为L1、L2、……、Ln. 未切割木板的长度恰好为切割木板的长度和。每次切断木板时，需要的开销为这块木板的长度。例如，长度为21的木板切割成5、8、8的三块木板。长为21的木板切割成13、8时，开销为21.再将长度为13的木板切割成长度5、8时，开销为13.于是合计开销为34。于是按题目要求将木板切割完，最小的开销是多少？
限制条件：
1<=N<=2000
0<=Li<=5000
输入样例：
N=3, L={8, 5, 8}
输出样例：
34
由于木板的切割顺序不确定，切割方法有很多，题目看似很难入手。然而，仔细考虑会发现我们可以用贪心算法来解决此问题。
我们可以利用二叉树原理来描述切割木板。
文章图片
根据这个二叉树的切割方法，可以计算出总开销：
3 ? 2 + 4 ? 2 + 1 ? 3 + 2 ? 3 + 5 ? 2 = 33 3*2+4*2+1*3+2*3+5*2=33 3?2+4?2+1?3+2?3+5?2=33
根据此二叉树我们可观察到，如果想要总开销最小，最短的板应该是最深的叶子节点，而且该叶子节点一定右兄弟节点，说以该兄弟节点一定是次短板。
因此我们可以哈夫曼编码的方式来构造二叉树：
- 首先将L1~Ln排序
- 取最短的两个节点合并
- 重新排序，并重复步骤二
#include
#include#define MAX_N 1000
using namespace std;
int N, L[MAX_N];
void init(){
cin>>N;
for(int i=0;
i>L[i];
}
}bool complare(int a,int b){
return a>b;
}
void solve(){//利用sort函数排序
sort(L,L+N,complare);
//从大到小排序
int ans=0;
while(N!=1){//循环合并最小的两个节点
L[N-2]+=L[N-1];
N--;
ans+=L[N-1];
sort(L,L+N,complare);
}
cout<1){
int mii1 =0, mii2=1;
if(L[mii1] >L[mii2]) swap(mii1,mii2);
//找出最小的两个数
for(int i=2;
i
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- Bootstrap_栅栏格
- java|Java多线程确保子线程执行完再执行-循环栅栏CyclicBarrier
- Fence Repair POJ - 3253 （贪心！！哈夫曼最小二叉树）
- USACO算法系列十九——fence4
- poj3253
- 骑马修栅栏
- ————ACM训练————|POJ 3253 fence Repair 一个很有趣的贪心解法
- 编程算法 - 篱笆修理(Fence Repair) 堆(heap) 代码(C++)
- 编程算法 - 篱笆修理(Fence Repair) 代码(C)
- ————ACM————|POJ3253 Fence Repair （二叉堆 | 优先队列 | huffman树 )