首页 > 代码库 > poj2299解题报告(归并排序求逆序数)

poj2299解题报告(归并排序求逆序数)

 

 

POJ 2299,题目链接http://poj.org/problem?id=2299

题意:

给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列。

思路:

其实就是求逆序数,那么直接向到的就是冒泡了,交换一次,记录一次即可。但是n的范围达到50W,冒泡O(n^2)的复杂度铁定超时

然后、、、发现曾经微软有一道笔试题类似就是求逆序数的,对,没错,用归并。

例:合并两个序列(1,3,5)(2,4,6),新序列第二个元素是2,那么它和它前面的35形成了逆序数对,所以....

代码:

//3880K	391MS#include <cstdio>#include <algorithm>int buf[500000];int ret[500000];unsigned long long count;void mergeArray(int *a, int first, int mid, int last, int *ret){	int i = first, j = mid+1, k =0;	int m = mid,   n = last;	while(i<=m && j<=n){		if (a[i] <= a[j]) {			ret[k++] = a[i++];		}		else {			ret[k++] = a[j++];			count += m-i+1;   //记录		}	}	while(i<=m) ret[k++] = a[i++];	while(j<=n) ret[k++] = a[j++];	for (int i=0;i<k; ++i) a[first+i] = ret[i];}void mergeSort(int data[], int first, int end, int *ret){	if (first < end)	{		int mid = (first + end)/2;		mergeSort(data, first, mid, ret);		mergeSort(data, mid+1, end, ret);		mergeArray(data, first, mid, end, ret);	}}int main(){	int num;	while (true)	{		scanf("%d", &num);		if (num <= 0) break;		for (int i=0; i<num; ++i) scanf("%d", &buf[i]);		count = 0;		mergeSort(buf, 0, num-1, ret);		printf("%lld\n", count);	}	return 0;}