比赛 noip2016普及练习2 评测结果 AAAAAAAAAA
题目名称 排序测试 最终得分 100
用户昵称 Furyton 运行时间 9.817 s
代码语言 C++ 内存使用 15.57 MiB
提交时间 2016-11-07 21:18:56
显示代码纯文本
#include <iostream>
#include <cstdio>
using namespace std;

const int maxn=2000000+10;
int n,ans;
int a[maxn],b[maxn];
void merge(int,int,int);
int main()
{
	freopen("sorttest.in","r",stdin);
	freopen("sorttest.out","w",stdout);

	scanf("%d",&n);
	for(int i=0; i!=n; ++i)
	{
		scanf("%d",&a[i]);
	}
	merge(0,(n-1)/2,n-1);

	for(int i=0; i!=n; ++i)
		printf("%d ",b[i]);
	return 0;
}
void merge(int l,int mid,int r)
{
	if(l==r)return;
	merge(l,(l+mid)/2,mid);
	merge(mid+1,(mid+1+r)/2,r);

	int i=l,j=mid+1,k=l;
	while(i<=mid && j<=r)
	{
		if(a[i]<=a[j])
		{
			b[k]=a[i];i++;
			ans+=j-(mid+1);
		}
		else
		{
			b[k]=a[j];j++;
		}
		k++;
	}
	while(i<=mid)
	{
		b[k]=a[i];i++;k++;
		ans+=r-mid;
	}
	while(j<=r)
	{
		b[k]=a[j];j++;k++;
	}
	for(int i=l; i<=r; i++)
		a[i]=b[i];
}