对于一个包含N个非负整数的数组A[1..n]，如果有i < j，且A[ i ]>A[ j ]，则称( i , j )为数组A中的一个逆序对。
例如，数组（3，1，4，5，2）的逆序对有(3,1),(3,2),(4,2),(5,2)，共4个。
输入格式:
输入包含若干组数据，第一行为一个整数T（0<T<20），表示共有T组测试数据。接下来每组测试数据包括两行，第一行只有一个整数m（0<m<=1000），表示数组有m个数，第二行为m个整数，数据之间用空格分隔。
输出格式:
对输入中的每组测试数据，输出一行对应逆序对的个数。
输入样例:
在这里给出一组输入。例如：
2
5
3 1 4 5 2
10
1 2 3 4 5 6 7 8 9 10
输出样例:
在这里给出相应的输出。例如：
4
0
代码长度限制
16 KB
时间限制
1000 ms
内存限制
64 MB
栈限制
8192 KB
#include <stdio.h>// 合并两个子数组并计数逆序对
int Count(int arr[], int temp[], int left, int mid, int right)
{int i = left; // 左子数组的起始索引int j = mid + 1; // 右子数组的起始索引int k = left; // 临时数组的起始索引int inv_count = 0;while ((i <= mid) && (j <= right)){if (arr[i] <= arr[j]){temp[k++] = arr[i++];}else{temp[k++] = arr[j++];inv_count += (mid - i + 1); // 统计逆序对}}while (i <= mid){temp[k++] = arr[i++];}while (j <= right){temp[k++] = arr[j++];}for (i = left; i <= right; i++){arr[i] = temp[i];}return inv_count;
}// 递归地分割数组并计数逆序对
int Sort(int arr[], int temp[], int left, int right)
{int mid, inv_count = 0;if (left < right){mid = (left + right) / 2;inv_count += Sort(arr, temp, left, mid);inv_count += Sort(arr, temp, mid + 1, right);inv_count += Count(arr, temp, left, mid, right);}return inv_count;
}// 主函数
int main()
{int T;scanf("%d", &T);while (T--){int m;scanf("%d", &m);int arr[m];for (int i = 0; i < m; i++){scanf("%d", &arr[i]);}int temp[m];int inv_count = Sort(arr, temp, 0, m - 1);printf("%d\n", inv_count);}return 0;
}