比赛 noip2016普及练习2 评测结果 AAAAATTTTT
题目名称 排序测试 最终得分 50
用户昵称 king'back 运行时间 12.427 s
代码语言 C++ 内存使用 15.57 MiB
提交时间 2016-11-07 19:58:31
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn=2000000+1;
int a[maxn],b[maxn];
int n;
void merge(int l,int r);
void mergesort(int l,int mid,int r);
int main()
{
	freopen ("sorttest.in","r",stdin);
	freopen ("sorttest.out","w",stdout);
	
	cin>>n;
	for (int i=1; i<=n; i++)
		cin>>a[i];
	merge(1,n);
	for (int i=1; i<n; i++)
		cout<<a[i]<<' ';
	cout<<a[n]<<endl;
	return 0;
}
void merge(int l,int r)
{
	if (l==r) return;
	int mid=(l+r)/2;
	merge(l,mid);
	merge(mid+1,r);
	mergesort(l,mid,r);
}
void mergesort(int l,int mid,int r)
{
	int i=l,j=mid+1,len=l;
	while (i<=mid && j<=r)
	{
		if (a[i]<a[j])
		{
			b[len]=a[i];len++;i++;
		}
		else
		{
			b[len]=a[j];len++;j++; 
		}
	}
	while (i<=mid)
	{
		b[len]=a[i]; len++; i++;
	}
	while (j<=r)
	{
		b[len]=a[j]; len++; j++; 
	}
	for (int k=l; k<=r; k++)
		a[k]=b[k];
}