用归并排序求逆序数.txt

来自「ACM资料大集合」· 文本 代码 · 共 57 行

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

//用归并排序求逆序数 NOJ 1022
#define NMAX 500005
long a[NMAX];
long tt[NMAX];//暂存数组
__int64 ans;

void Merge(long *sr,long s,long m,long t)
{
	long k,p,q;
	//使用暂存数组存储排序好的部分数
	for(k=s,p=m+1,q=s;k<=m&&p<=t;)
	{	
		if(sr[k]<=sr[p]) {tt[q++]=sr[k++];}
		else {tt[q++]=sr[p++];ans+=m-k+1;}//根据移动位置求逆序数
	}
	while(k<=m) tt[q++]=sr[k++];
	while(p<=t) tt[q++]=sr[p++];
	//覆盖原数组
	for(k=s;k<=t;k++) sr[k]=tt[k];
}

void msort(long *sr,long s,long t)
{
	long m;
	if(s<t)
	{
		m=(s+t)/2;
		msort(sr,s,m);
		msort(sr,m+1,t);
		Merge(sr,s,m,t);
	}
}


int main()
{
	long num,i;
	scanf("%ld",&num);
	while(num!=0)
	{
		ans=0;
		memset(a,0,sizeof(a));
		for(i=1;i<=num;i++)
			scanf("%ld",&a[i]);
		msort(a,1,num);
		printf("%I64d\n",ans);
		scanf("%ld",&num);
	}
	return 0;
}