POJ 3253 Fence repair

POJ 3253 Fence repair 题目

分析

每次分割的开销等于自己的长度，其实也等于切割后的小板的长度，那么如果使每次切割的小班的长度组合起来最小，就可以实现每次切割长度最小

于是就把问题转化为——>每次求解最短板与第二短板组合
（类比哈夫曼树）

代码1

普通for循环实现，时间复杂度为n²

#include
using namespace std;
typedef long long int ll;
#define N 99999999
int n ,L[N];

void sovle() {
	ll ans=0;//计算开销的 
	while(n>1) { //直到木板的数量为1
	
		//求出最短和第二短板
		int min1=0,min2=1;
		if(L[min1]>L[min2])//计算数组中第0块和第1块的大小
			swap(min1,min2);
		for(int i=2; in;
	for(int i=0; i>L[i];//每块木板的长度
	sovle();
}

代码2

同样的思路，但是采用优先队列实现，算法的时间复杂度为nlongn

#include
#include 
#define N 999999
typedef long long ll;
using namespace std;
int n,L[N];
void solve(){
	ll ans=0;
	
	//声明一个取值为从小到达的优先数列 
	priority_queue,greater> Q;
	for(int i=0;i1){
		int l1,l2;
		l1=Q.top();Q.pop();
		l2=Q.top() ;Q.pop() ;
		ans+=l1+l2;
		Q.push(l1+l2);  
	} 
	cout<>n;
	for(int i=0;i>a[i];
	solve();
}