2386.cpp

来自「自己的ac代码 在acm.zju.edu.cn 上的题目」· C++ 代码 · 共 57 行

#include<stdio.h>
int a[500005],left[500005],right[500005];
long long  cnt;
void Merge(int l,int m,int r)
{
	int i,j,k;
	for(i=l;i<=m;i++)left[i]=a[i];
	left[i]=0x7fffffff;
	for(i=m+1;i<=r;i++)right[i]=a[i];
	right[i]=0x7fffffff;
	k=l;i=l;j=m+1;
	while(k<=r)
	{
		if(left[i]<=right[j])a[k++]=left[i++];
		else {a[k++]=right[j++];cnt+=m-i+1;}
	}
}


void Sort(int l,int r)
{
	if(l<r)
	{
		int mid=(l+r)/2;
		Sort(l,mid);
		Sort(mid+1,r);
		Merge(l,mid,r);
	}
}



int main()
{
	int i,j,k;
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)break;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			
		}
		cnt=0;
		Sort(1,n);
		
		printf("%lld\n",cnt);



	}
	return 0;
}