木棒分割.cpp

ACM习题 木棒分割的源代码

/*
题目 - 木棒分割   
 
描述 
小T要把一根长木棒分割成n段,首先把长木棒分割成两段,然后每次从分割出来木棒中取出一根来分割成两段,最后得到n段.把一根长为m的木棒分成两段的费用为m.小T希望分割的费用尽可能少,请你找到这个最小费用.
 
关于输入 
第一行是一个整数n(1<=n<=10000),表示分割成多少段. 
接下来一行n个正整数,表示分割成的每一段的长度. 
长木棒的长度等于这n个数的和,分割中不会有损失.
 
关于输出 
输出一个正整数,表示分割所需的总费用
 
例子输入 
5
1 2 3 4 5
 
例子输出 
33
 
提示 
原始木棒的长度为15,首先分割为6和9两段(费用15),然后把长为9的分成4和5两段(费用9),接着把长为6木棒分为3和3两段(费用6),最后把长为3的一段分为1和2两段(费用3). 
总费用为:15 + 9 + 6 + 3 = 33 
*/
#include<iostream>
using namespace std;
class MinHeap{//最小堆ADT定义
private:
	int* heapArray;       //存放堆中元素
	int CurrentSize;	//当前堆中元素数目
	int MaxSize;		//堆所能容纳的最大元素数目
public:
	MinHeap(int *T,int n);			//构造函数,n表示初始化堆的最大元素数目
	MinHeap(){						//缺省构造函数
		heapArray=NULL;
	}
	~MinHeap(){delete []heapArray;}			//析构函数
	bool isLeaf(int pos) const;				//如果是叶结点，返回TRUE
	int leftchild(int pos) const;			//返回左孩子位置
	int rightchild(int pos) const;			//返回右孩子位置
	int parent(int pos) const;				//返回父结点位置
	bool Insert(int);			//向堆中插入新元素newNode
	int RemoveMin();							//从堆顶删除最小值
	//从pos向上开始调整，使序列成为堆
	void SiftUp(int pos){				
		int tempPos=pos;
		int temp=heapArray[tempPos];
		while((tempPos>0)&&(heapArray[parent(tempPos)]>temp)){
			heapArray[tempPos]=heapArray[parent(tempPos)];
			tempPos=parent(tempPos);
		}
		heapArray[tempPos]=temp;
	}
	//筛选法函数，参数left表示开始处理的数组下标
	void SiftDown(int left){
		int i=left,					//标识父结点的位置
			j=2*i+1;				//标识关键值较小的子结点
		int temp=heapArray[i];		//保存父结点
		while(j<CurrentSize){		//过筛
			//j指向数值较小的子结点
			if((j<CurrentSize-1)&&(heapArray[j]>heapArray[j+1])) j++;
			if(temp>heapArray[j]){
				heapArray[i]=heapArray[j];
				i=j;       j=2*j+1;	//向下继续
			}
			else break;
		}
		heapArray[i]=temp;
	}
};						
MinHeap::MinHeap(int *T ,int n){//构造函数
	if(n<=0) return;
	CurrentSize=0;
	MaxSize=n;							//初始化堆容量为n
	heapArray=new int[MaxSize];			//创建堆空间
	for(int i=0;i<n;i++){
		Insert(T[i]);
	}
}						
bool MinHeap::isLeaf(int pos) const{			//判断是否叶结点
	return (pos>=CurrentSize/2)&&(pos<CurrentSize);
}						//返回当前结点做孩子位置
int MinHeap::leftchild(int pos) const{
	return 2*pos+1;
}						//返回右孩子位置
int MinHeap::rightchild(int pos) const{
	return 2*pos+2;
}						//当前结点得返回父结点位置
int MinHeap::parent(int pos) const{
	return (pos-1)/2;
}					//向堆中插入新元素newNode
bool MinHeap::Insert(int newNode){
	if(CurrentSize==MaxSize) return false;//堆空间已经满
	heapArray[CurrentSize]=newNode;
	SiftUp(CurrentSize);				//向上调整
	CurrentSize++;
	return true;
}
int MinHeap::RemoveMin(){				//从堆顶删除最小值
	if(CurrentSize==0){		//空堆
		return 0;
	}
	else{
		int temp=heapArray[0];			//保存堆顶最小元素
		heapArray[0]=heapArray[--CurrentSize];//使堆顶元素等于最后一个元素
		if(CurrentSize>1)	SiftDown(0);	//从堆顶开始筛选
		return temp;
	}
}
int main()
{
	int n,i;
	cin>>n;
	int *length=new int [n];
	for(i=0;i<n;i++) cin>>length[i];
	int totalCost=0;
	MinHeap Heap(length,n);
	int a=0,b=0,c=0;
	while(n>1){
		a=Heap.RemoveMin();
		b=Heap.RemoveMin();
		c=a+b;
		Heap.Insert(c);
		totalCost+=c;
		n--;
	}
	cout<<totalCost<<endl;
	return 0;
}