zcmu--1203: 逆序数（归并排序）

1203: 逆序数

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 565  Solved: 117

[Submit][Status][Web Board]

Description

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数不小于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。

Input

多组测试数据

每组测试数据分两行，第一行一个正整数n（n <= 50000)

第二行有n个元素( 0 <= A[i] <= 10^9)

Output

每组测试数据输出一行表示逆序数

Sample Input

4 2 4 3 1 3 1 1 1

Sample Output

4 3

HINT

//归并排序
#include<stdio.h>
#include<string.h>
#define maxsize 50005
int a[maxsize],b[maxsize];            //题目上虽然数据类型比较大，一开始想用long long，但是函数形参范围太大可能会//有错误，而且用int也A了，可能没关系
int cnt;void mergearray(int*a,int first,int last)
{   int i=first,mid=(first+last)/2;int j=mid+1,k=first;while(i<=mid&&j<=last){if(a[i]<a[j])b[k++]=a[i++];else {cnt+=j-k;b[k++]=a[j++];//printf("cnt=%d\n",cnt);}}while(i<=mid)b[k++]=a[i++];while(j<=last)b[k++]=a[j++];for(i=first;i<=last;i++)        //一开始这里写的是i=0;i<=k;然后答案不对；a[i]=b[i];//printf("mergearray\n");
}
void mergesort(int *a,int first,int last)
{if(first<last){//printf("mergesort\n");int mid=(first+last)/2;mergesort(a,first,mid);mergesort(a,mid+1,last);mergearray(a,first,last);}    
}int main()
{int n;while(scanf("%d",&n)!=EOF){cnt=0;memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(int i=0;i<n;i++)scanf("%lld",a+i);mergesort(a,0,n-1);printf("%d\n",cnt);}return 0;
}

代码段 小部件

[Dàimǎ duàn xiǎo bùjiàn]

Code section widget