陈顺凡-6分.txt

这是很不错的计算机算法

#include <iostream>
#include <fstream>
using namespace std;

int *s;      //定义动态数组－存储各堆石子的数量
int *sMin;
int k;


void sift(int first , int length)
{//调整序列s[first..length]使之满足堆排序的性质。
    int r,p;
    int temp;

	r=first;
    p=2*r;
	while(r <= length/2){
		if(r==length/2){  //r只有一个儿子
			if (s[r] > s[2*r]){
               temp=s[2*r];
			   s[2*r]=s[r];
			   s[r]=temp;
			}
			r=length;
		}
		else{  //r有两个儿子2r和2r+1
            if((s[r]>s[2*r]) && (s[2*r]<=s[2*r+1])){
               temp=s[2*r];
			   s[2*r]=s[r];
			   s[r]=temp;
			   r=2*r;
			}
			else{
				if((s[r]>s[2*r+1])&&(s[2*r+1]<s[2*r])){
                   temp=s[2*r+1];
			       s[2*r+1]=s[r];
			       s[r]=temp;
			       r=2*r+1;
				}
				else{
					r=length;
				}
			}
		}
	}
}

void heapsort(int n)
{//对s[1..n]进行堆排序
    int i;
	int temp;

	//建立初始堆
	for (i=n/2 ; i>=1 ; i--)
		sift(i,n);
   //输出堆排序，结果是从大到小
	for( i=n; i>=2 ; i--){
        temp=s[i];
		s[i]=s[1];
		s[1]=temp;
		sift(1, i-1);
	}
}

//参数x: 待插入石子堆的石子数并调整序列成堆；参数length表示堆数组的当前长度；a: 堆数组
void insert(int x , int & length , int * &a)
{
    int i;
	int temp;
 
    length++;
	a[length]=x;
	i=length;
	while((i>1)&&(a[i]<a[i/2]))
	{
		temp=a[i];
		a[i]=a[i/2];
		a[i/2]=temp;
		i=i/2;
	}

}

//
int deleteMin(int & length , int * &a)
{//删除并返回最小数的石子堆，并调整序列成堆
	int i,j;
	int temp;
	int minimum;

	if (length==0)
	{
		minimum = -1; 
	}
	minimum = a[1];//取出堆顶的最小元素
	a[1]=a[length];//把最后一个元素替换堆顶元素
	length--;//当堆元素的个数减1
	i=1;
	//调整堆
	while(i<=length/2)
	{
		if((a[2*i]<a[2*i+1])||(2*i == length)) 
		{
			j=2*i;
		}else
		{
            j=2*i+1; //j是i的具有较高优先级的儿子。当i只有一个儿子时，j是i的唯一儿子
		}
		if(a[i]>a[j])
		{
			temp=a[i];
			a[i]=a[j];
			a[j]=temp;
			i=j;
		}else
		{
			return minimum;//不能再往下推
		}
	}
	return minimum;       //已经到叶节点了

}

int minValue(int k,int & length, int * &a)
{//求出最小合并费用
	int tempValue;
	int sum=0;
    int x,y;

	for(int i=1;i<k;i++)
	{
		x=deleteMin(length,a);
		y=deleteMin(length,a);
        tempValue=x+y;
		sum = sum+tempValue;
        insert(tempValue,length,a);
	}
	return sum;
}
//主程序
void main()
{
	int n ;    //标识待合并的石子堆数
	int length;  //标识堆的长度
	int min;
	ifstream fin("input.txt");
	ofstream out("output.txt");
	if(fin.fail())
	{
		cout<<"the input.txt is not exist!";
		exit(1);
	}
	fin >> n ;//石子堆数量
	s=new int[n+1];
	sMin=new int[n+1];

   for(int i=1;i<=n;i++)
	{
		fin >> s[i];//每堆石子的数量
	}
    heapsort(n);
	for(i=1;i<=n;i++)
	{
		sMin[i]=s[n-i+1];//因为堆排序的结果是从大到小，所以这里对堆排序结果进行倒序
	}
	length=n;
    min=minValue(n,length,sMin);
	out<<min;
	fin.close;
	out.close;
	delete []s;
	delete []sMin;
}