孙锋-6分.txt

这是很不错的计算机算法

#include<fstream.h>
#include<stdlib.h> 
#include<stdio.h>
int n;
int *data;
void readData()
{
	ifstream inStream;
	inStream.open("input.txt");

	if(!inStream)
	{
		cerr << "Error open file.\n";
		return;
	}

	inStream >> n;
	data = new int[n+2];
	data[0]=n;
	for(int i=1; i<=n; i++)
	{
		inStream >> data[i];
	}
	inStream.close();
}
void writeData(int i)
{     
    ofstream outStream;
	outStream.open("output.txt");

	//如果打开文件失败，那么输出提示信息；
	if(!outStream)
	{
		cerr << "Error open file.\n";
		return;
	}
	outStream<<i<<endl;
	outStream.close();	
}
//在排好序的序列中排序
void seqPartition(int a[])
{
	int i=a[0];
	int j=a[i];
	int m=i-1;
    while(m>0&&a[m]<j)m--;
	for(int k=i;k>m;k--)a[k]=a[k-1];
	a[m+1]=j;
}

//第一次数据进行快速排序
int Partition(int L[],int low,int high)
{
	L[0]=L[low];
	int pivokey=L[low];
	while(low<high)
	{while(low<high&&L[high]<=pivokey)--high;
	 L[low]=L[high];
	 while(low<high&&L[low]>=pivokey)++low;
	 L[high]=L[low];}
	L[low]=L[0];
	return low;
}

void QSort(int L[],int low,int high)
{   int pivotloc;
	if(low<high){
		pivotloc=Partition(L,low,high);
		QSort(L,low,pivotloc-1);
		QSort(L,pivotloc+1,high);
	}
}
//计算
void merge(int a[])
{

	int j=a[0];
	a[j-1]=a[j]+a[j-1];a[n+1]=a[n+1]+a[j-1];
	a[0]=a[0]-1;
	seqPartition(a);
	while(a[0]>1)merge(a);
}

void main()
{readData();
 QSort(data,1,n);
 data[0]=n;data[n+1]=0;
 merge(data);
 writeData(data[n+1]);
}