王承浩-6分.txt

这是很不错的计算机算法

/*  merge2
问题描述：
见merge2.pdf

算法设计：
1、先将输入的数组a[0:n-1]采用快速排序方法进行降序排列（n为数组长度）
2、取得最后两位进行相加，将结果sum累加至变量counter中
3、数组长度减少1，且末元素的值变为sum
4、对新的数组按照大小进行递减排序（只需对sum进行排序即可）
5、如果n>=2，则重复步骤2至步骤4
6、如果n<2，则程序结束，counter的值即为最终解，将其输入到output.txt文件中
*/
#include <stdlib.h>
#include <fstream.h>

ofstream out("output.txt");//创建输出文件

//交换数组中2元素的函数
void swap(int a[],int i,int j);

//对数组进行划分的函数，返回一个基准元素x，数组a[]中比x小的移动到x右边，比x大的移动到x左边
//参数1：要排序的数组
//参数2：起始元素下标
//参数3：结束元素下标
int partition(int a[],int p,int r);

//快速排序算法（排序结果为递减顺序）
//参数1：要排序的数组
//参数2：起始元素下标
//参数3：结束元素下标
void quickSortDesc(int a[],int p,int r);

//对数组a重新进行降序排列（只对最后一个元素进行插入排序）
void reSortDesc(int a[],int n);

//计算将n堆石子合并成一堆的最小总费用的函数，返回值即为最终解
int merge2(int a[],int n);

//主函数
int main(){
	ifstream fin("input.txt",ios::nocreate);//打开输入文件
	int n;//数组长度

	if(!fin){
		cerr<<"the input file is not exist!"<<endl;
		return -1;
	}
	else{
		fin>>n;
	}

	int *a;
	a = new int[n];
	int i;
	//读入数据
	for(i=0;i<n;i++){
		fin>>a[i];
	}

	quickSortDesc(a,0,n-1);//对数组进行降序排列
	
	int mixFee = merge2(a,n);//计算最小总费用

	out<<mixFee;//将结果输出到output.txt文件

	delete[] a;

	fin.close();
	out.close();

	return 0;
}

void swap(int a[],int i,int j){
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

void quickSortDesc(int a[],int p,int r){
	if(p<r){
		int q = partition(a,p,r);
		quickSortDesc(a,p,q-1);
		quickSortDesc(a,q+1,r);
	}
}

int partition(int a[],int p,int r){
	int i = p;
	int j = r+1;

	int x = a[p];

	while(true){
		while(a[++i]>x);
		while(a[--j]<x);

		if(i>=j)break;
		swap(a,i,j);
	}

	a[p] = a[j];
	a[j] = x;

	return j;
}

int merge2(int a[],int n){
	int counter = 0;
	int len = n;
	
	if(n>=2){
		counter = a[n-1]+a[n-2];
		
		a[n-2] = counter;

		reSortDesc(a,n-1);//对新数组重新进行降序排序

		counter += merge2(a,n-1);//递归调用
	}
	else{
		return 0;
	}

	return counter;
}

void reSortDesc(int a[],int n){
	int temp = a[n-1];
	int i = n-2;
	while(i>=0){
		if(temp>a[i]){
			a[i+1] = a[i];
			if(i==0){
				a[i] = temp;
			}
		}
		else{
			a[i+1] = temp;
			break;
		}
		i--;
	}
}