逆序对

链接：https://www.nowcoder.com/questionTerminal/f50f89c3b4624cd6aa3312747cd45879 来源：牛客网

给定一个长度为n的排列A,逆序的定义：(i,j)为逆序对，当i<j && A[i]>A[j]

求排列A的逆序对数量。

输入描述:

第一行一个整数n，表示排列的长度. 第二行n个元素，表示A排列.

输出描述:

输出逆序对的数量

示例1

输入

5 3 2 4 1 5

输出

4

解析：原理是归并排序，在每次merge之前，比较左右两边的大小，若出现当i<j && A[i]>A[j] ，则逆序对数量加一。

#include<bits/stdc++.h> using namespace std; long mergeSort(int a[],int n); long sortProcess(int a[],int L,int R); long merge(int a[],int L,int mid,int R); int main() { int n; cin>>n; int a[n]; for(int i=0;i<n;i++) cin>>a[i]; cout<<mergeSort(a,n)<<endl; return 0; } long mergeSort(int a[],int n) { if(a==NULL||n<2) return 0; return sortProcess(a,0,n-1); } long sortProcess(int *a,int L,int R) { if(L>=R) return 0; int mid=L+((R-L)>>1);//相当于(L+R)/2,可有效避免溢出 return sortProcess(a,L,mid)+sortProcess(a,mid+1,R)+merge(a,L,mid,R); } long merge(int *a,int L,int mid,int R) { int help[R-L+1];//保存每次merge后的数组 memset(help, 0, sizeof(help)); int i=0; int p1=L; int p2=mid+1; long rul=0; while(p1<=mid&&p2<=R) { //设任意p1<m<mid,当a[p1]>a[p2]时，a[m]<a[p2]也显然成立，m的数量为 mid-p1+1 //rul+=a[p1]<=a[p2]?(R-p2+1)*a[p1]:0; rul+=a[p1]>a[p2]?(mid-p1+1):0; help[i++]=a[p1]<=a[p2]?a[p1++]:a[p2++];//每次选择小的数字存入数组 } //左右两边的数量不是每次都相等，将剩下的元素也添加到help数组中 while(p1<=mid) { help[i++]=a[p1++]; } while(p2<=R) { help[i++]=a[p2++]; } for(i=0;i<R-L+1;i++) a[L+i]=help[i]; return rul; }