分而治之：逆序对计数问题

分而治之：逆序对计数问题

问题： 输入一个长度长度为n的数组A[n]，求出数组A[n]逆序对的总数。 输入： 长度为n的数组A[n] 输出： 数组A[n]逆序对的总数

问题分析：

把数组A二分为两个子数组A[1…n/2],A[n/2 + 1…n]递归求解子问题 求解S1∶仅在A[1…n/2]中的逆序对数目 求解S2∶仅在A[n/2+1…n]中的逆序对数目合并A[1…n/2]和A[n/2 +1…n]的解 求解S3∶跨越子数组的逆序对数目 S = S1+S2+S3

与最大子数组的问题一样，执行效率的瓶颈值也在合并方面，也就是S3跨越子数组的逆序对数目的求解问题。

S3的求解：

1. 策略一:直接求解 (1)对每个Aj]∈ A[m +1…n]，枚举A[i]∈ A[1…m]并统计逆序对数目 (2)求解S的算法运行时间:O(n²) 直接求解的运行时间不是很理想，所以，有没有更好的方法呢？

2. 策略二:排序求解 (1)分别对数组A[1…m]和A[m+ 1…n]进行排序； (2)对于每个A[ j ]∈A[m+1…n]，采用二分查找为其在A[1…m]中定位； (3)A[ j ]在A[1…m]定位点右侧的元素均可与A[ j ]构成逆序对； (4)求解S的算法运行时间:O(nlogn)。

排序求解S的分而治之提高了算法运行时间，但仍然还有优化的可能；

3. 策略三:归并求解 (1)从左到右扫描有序子数组:A[i]∈A[1…m]，A[j] ∈ A[m+1…n] ···如果A[i] > A[j]，统计逆序对，j向右移 ···如果A[i] ≤ A[j]，i向右移 (2)利用归并排序框架保证合并后数组的有序性 (3)S时间复杂度降至O(n)

算法分析图：

代码

#include <iostream> #include <cstdio> using namespace std; const int N = 10000; int a[N],b[N]; int count; void Merge(int a[], int l, int mid , int r) //归并排序的合并部分 { int i = l, j = mid + 1,k = l; //遍历统计逆序数对 while(i <= mid&&j <= r){ if(a[i] <= a[j]) b[k++] = a[i++]; else{ count += j - k; b[k++] = a[j++]; } } while(i <= mid) //左半部分排序 b[k++] = a[i++]; while(j <= r) //右半部分排序 b[k++] = a[j++]; for(int i = l; i <= r; i++) //从辅助空间复制回 a 数组 a[i] = b[i]; } void MergeSort(int a[], int l, int r) //归并排序 { if(l < r){ int mid = l + (r-l)/2; MergeSort(a,l,mid); // 左半部分递归求解 MergeSort(a,mid+1,r); // 右半部分递归求解 Merge(a,l,mid,r); // 合并前后两个部分 } } int main(){ int n; cin >> n; for(int i = 0; i < n; i++) scanf("%d", &a[i]); MergeSort(a,0,n-1); cout << count; return 0; }

例题：求逆序数

题目描述 在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

现在，给你一个N个元素的序列，请你判断出它的逆序数是多少。

比如 1 3 2 的逆序数就是1。

输入 第一行输入一个整数T表示测试数据的组数（1<=T<=5) 每组测试数据的每一行是一个整数N表示数列中共有N个元素（2〈=N〈=1000000） 随后的一行共有N个整数Ai(0<=Ai<1000000000)，表示数列中的所有元素。

数据保证在多组测试数据中，多于10万个数的测试数据最多只有一组。 输出 输出该数列的逆序数 样例输入 2 2 1 1 3 1 3 2 样例输出 0 1

代码：

#include <iostream> #include <cstdio> using namespace std; #define max 1000001 long long a[max],b[max]; long long count; void Merge(long long a[], int l, int mid , int r) //归并排序的合并部分 { int i = l, j = mid + 1,k = l; //遍历统计逆序数对 while(i <= mid&&j <= r){ if(a[i] <= a[j]) b[k++] = a[i++]; else{ count += j - k; b[k++] = a[j++]; } } while(i <= mid) //左半部分排序 b[k++] = a[i++]; while(j <= r) //右半部分排序 b[k++] = a[j++]; for(int i = l; i <= r; i++) //从辅助空间复制回 a 数组 a[i] = b[i]; } void MergeSort(long long a[], int l, int r) //归并排序 { if(l < r){ int mid = l + (r-l)/2; MergeSort(a,l,mid); // 左半部分递归求解 MergeSort(a,mid+1,r); // 右半部分递归求解 Merge(a,l,mid,r); // 合并前后两个部分 } } int main(){ int n; for(int i = 0; i < n; i++) scanf("%d",&a[i]); MergeSort(a,0,n-1); printf("%lld\n",count); return 0; } int main(){ int n,m; scanf("%d",&n); while(n--){ scanf("%d",&m); count = 0; for(int i = 0; i < m; i++) scanf("%d",&a[i]); MergeSort(a,0,m-1); printf("%lld\n",count); } return 0; }