原题
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。
输入
第1行：N，N为序列的长度（n <= 50000)
第2 - N + 1行：序列中的元素（0 <= A[i] <= 10^9）
输出
输出逆序数
输入样例
4
2
4
3
1
输出样例
4
开始分析
不知道大家有没有写过二路归并排序的题目。如果做过那么接下来你看起来就会很简单。否则会很吃力。
在这里放一个左神讲解这些题目的一个连接，想看的可以看一下。时间比较长。
连接
二路归并排序代码
#include <iostream>
using namespace std;void merge(int arr[],int l,int mid,int r){int help[r-l+1];int i = 0;int p1 = l;int p2 = mid+1;while(p1 <= mid&&p2 <= r){help[i++] = arr[p1] <= arr[p2] ? arr[p1++]:arr[p2++];}while(p1 <= mid){help[i++] = arr[p1++];}while(p2 <= r){help[i++] = arr[p2++];}for(i = 0;i < r-l+1;i++){arr[l+i] = help[i];}
}void process(int arr[],int l,int r){if(l == r){return ;}int mid = l+((r-l)>>1);process(arr,l,mid);process(arr,mid+1,r);merge(arr,l,mid,r);
}int main(void){int arr[] = {2,3,7,8,1,23,67,99,2,4,7,8,10};int len = sizeof(arr)/sizeof(arr[0]);process(arr,0,len-1);for(int i = 0;i < len;i++){cout<<arr[i]<<" ";}return 0;
}
不知道大家看没看我刚才给大家的二路归并排序算法。我的逆序数算法就是在这个的基础上多加了几行代码罢了。
我们先拿一个简单的例子：
arr[] = {3,5,7,2,4,6};
以这个数组为例子，开始讲解。
- 我们先把这个数组给他拆成两份。开始各自排序。
- 如果数组中只有一个数字时直接返回，此时必定是有序的。
- 如果两边的数组已经排序完毕（此时各自都是有序的），开始merge。
那么最终返回的必定是有序的数组。
那么我们的改动就是在第三步，即merge的时候，计算一下逆序的数字就可以了。
- 如果arr1[p1] > arr[p2]，那么说明产生了逆序数。在这里需要计数。
- 值得注意的一点是，如果p1位置数字是大于的，那么p1+1,p1+2…位置的数字也是大于p2位置的数字的（因为是有序的）。
- 所以计数的时候需要注意，计数时需要计从p1到左边数组的末尾的长度。
代码就是这样：
#include <bits/stdc++.h>
using namespace std;
//逆序数--可以用小和问题的思路来解题
//即采用二路归并排序const int N = 50000;
int arr[N];int merge(int arr[],int l,int mid,int r){int help[r-l+1];int p1 = l;int p2 = mid+1;int i = 0;int sum = 0;while(p1 <= mid&&p2 <= r){if(arr[p1] < arr[p2]){help[i++] = arr[p1++];}else if(arr[p1] > arr[p2]){help[i++] = arr[p2++];//此时有逆序数 sum += mid-p1+1;}else{help[i++] = arr[p2++];}}while(p1 <= mid){help[i++] = arr[p1++];}while(p2 <= r){help[i++] = arr[p2++];}i = 0;for(p1 = l;p1 < p2;p1++){arr[p1] = help[i++];}return sum;
}int process(int arr[],int l,int r){if(l == r){//此时数组中只有一个数字//因此就不存在逆序数了return 0; }int mid = l + ((r - l)>>1);int sum = 0;int end = process(arr,l,mid);
// cout<<end<<endl;sum = end;end = process(arr,mid+1,r);
// cout<<end<<endl;sum += end;return sum+merge(arr,l,mid,r);
}int main(void){int n;cin>>n;int i = 0;for(;i < n;i++){cin>>arr[i];}int sum = process(arr,0,n-1);cout<<sum<<endl;return 0;
}
