- 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
时间限制：1 秒
内存限制：32 兆
题目描述：
- 输入：
-
每个测试案例包括两行：第一行包含一个整数n，表示数组中的元素个数。其中1 <= n <= 10^5。第二行包含n个整数，每个数组均为int类型。
- 输出：
- 对应每个测试案例，输出一个整数，表示数组中的逆序对的总数。
- 样例输入：
-
4 7 5 6 4
- 样例输出：
-
5
分析：我们首先想到的是一种暴力算法，让数组中的每一个元素都与数组的其他所有元素进行比较，时间复杂度为o(n^2)，显然不满足题目要求，那么我们需要寻找更高效的算法。归并排序的时间复杂度为o(nlogn)，利用它的思想可以求得逆序对总数。归并排序是相邻两个有序块进行比较，然后合并，形成一个新的有序块。在两个有序块left和right块合为一个有序块的过程中，元素的位置会发生变化，通过记录right块的每个元素的位置变化，来得到合并后块的逆序对的数量。这样，我们就在归并排序的过程中，统计出了逆序对的数量。
#include <stdio.h> #include <stdlib.h> #define MAX 0x7fffffff int a[100010]; long long count; void merge( int p, int q, int r ) { int n1,n2,*left,*right,i,j,k; n1 = q - p + 1; n2 = r - q; left = (int*)malloc((n1+1)*sizeof(int)); right = (int*)malloc((n2+1)*sizeof(int)); for( i=0; i<n1; i++ ) left[i] = a[p+i]; for( i=0; i<n2; i++ ) right[i] = a[q+i+1]; left[n1] = MAX; right[n2] = MAX; for( i=0,j=0,k=p; k<=r; k++) if(left[i]<=right[j]) { a[k] = left[i]; i++; } else { count = count + q + 1 + j - k; //逆序对计数，在归并排序算法的基础上仅仅增加了这条语句 a[k] = right[j]; j++; } free(left); free(right); } void merge_sort( int p, int r ) { int q; if( p<r ) { q = ( p + r ) / 2; merge_sort( p, q ); merge_sort( q+1, r ); merge( p, q, r); } } int main() { int i,n; while(scanf("%d",&n)!=-1) { count = 0; for( i=0; i<n; i++ ) scanf("%d",&a[i]); merge_sort( 0, n-1 ); printf("%lld\n",count); } return 0; }上述归并排序的写法参考的是《算法导论》P17。
注意：全局变量count不能声明为int型，必须为long long型。因为题目中说数组最大为10^5，那么最大逆序对为(10^5-1)*10^5/2，这个数大约在50亿左右，超过了int型的表示范围。