首页 > 代码库 > NYOJ117 求逆序数

NYOJ117 求逆序数

求逆序数

时间限制:2000 ms  |  内存限制:65535 KB
难度:5
描述

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

现在,给你一个N个元素的序列,请你判断出它的逆序数是多少。

比如 1 3 2 的逆序数就是1。

输入
第一行输入一个整数T表示测试数据的组数(1<=T<=5)
每组测试数据的每一行是一个整数N表示数列中共有N个元素(2〈=N〈=1000000)
随后的一行共有N个整数Ai(0<=Ai<1000000000),表示数列中的所有元素。

数据保证在多组测试数据中,多于10万个数的测试数据最多只有一组。
输出
输出该数列的逆序数
样例输入
2
2
1 1
3
1 3 2
样例输出
0
1
来源
[张云聪]原创
上传者
张云聪

归并排序求逆序数。


#include <stdio.h>
#include <string.h>

#define maxn 1000010
#define inf 0x7fffffff
typedef long long LL;

int arr[maxn], left[maxn>>1], right[maxn>>1];
LL cnt;

void merge(int start, int end) {
	int mid = (start + end) >> 1;
	int i, j, k;
	memcpy(left, arr+start, sizeof(int) * (mid-start+1));
	memcpy(right, arr+mid+1, sizeof(int) * (end-mid));
	left[mid-start+1] = right[end-mid] = inf;
	for(k=start, i=j=0; k <= end; ++k)
		if(left[i] <= right[j]) {
			arr[k] = left[i++];
		} else {
			arr[k] = right[j++];
			cnt += mid-start+1 - i;
		}
}

void mergeSort(int start, int end) {
	if(start == end) return;
	int mid = (start + end) >> 1;
	mergeSort(start, mid);
	mergeSort(mid + 1, end);
	merge(start, end);
}

int main() {
	int t, n, i;
	scanf("%d", &t);
	while(t--) {
		scanf("%d", &n);
		for(i = 0; i < n; ++i)
			scanf("%d", &arr[i]);
		cnt = 0;
		mergeSort(0, n-1);
		printf("%lld\n", cnt);
	}
	return 0;
}


NYOJ117 求逆序数