(应用排序算法编程7.2.2)POJ 2299 Ultra-QuickSort(使用归并排序回计算逆序对的个数)

(应用排序算法编程7.2.2)POJ 2299 Ultra-QuickSort(使用归并排序来计算逆序对的个数)

/*
 * POJ_2299.cpp
 *
 *  Created on: 2013年11月1日
 *      Author: Administrator
 */

#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 500010;

typedef long long lolo;//这里不要使用int,因为a[i]的范围达到了999999999。在最坏的情况下,需要交换的次数已经不是int类型的数所能表示的了
lolo a[maxn],t[maxn];
lolo ans;

//归并排序..归并排序是分治思想的一个典型的应用
void my_sort(lolo l , lolo r){
	if(l == r){
		return ;
	}

	lolo mid = (l+r)/2;
	my_sort(l,mid);
	my_sort(mid+1,r);

	lolo i = l,j = mid+1,now = 0;
	while(i <= mid && j <= r){
		if(a[i] > a[j]){
			ans += (mid - i + 1);//当a[i]>a[j]时,a[i]后面的数都能与a[j]形成逆序对
			t[++now] = a[j++];
		}else{
			t[++now] = a[i++];
		}
	}

	while(i <= mid){
		t[++now] = a[i++];
	}

	while(j <= r){
		t[++now] = a[j++];
	}

	now = 0;
	for(i = l ; i <= r ; ++i){//将临时数组t[]中的数组复制到a[]数组中
		a[i] = t[++now];
	}
}

int main(){
	lolo n;

	while(scanf("%lld",&n)!=EOF,n){
		ans = 0;

		lolo i;
		for(i = 1 ; i <= n ;++i){
			scanf("%lld",&a[i]);
		}

		my_sort(1,n);
		printf("%lld\n",ans);
	}

	return 0;
}

本题如果使用搜索的思想来做,那么时间复杂度将达到o(n^2),因为给的数很大,这是很可能会TLE,所以我们需要摆脱搜索的思想,采用分治的方法来做...............