(应用排序算法编程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,所以我们需要摆脱搜索的思想,采用分治的方法来做...............