题目描述
给定一个长度为n的整数数列,请你计算数列中的逆序对的数量。
逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满足 i < j 且 a[i] >
a[j],则其为一个逆序对;否则不是。
输入格式
第一行包含整数n,表示数列的长度。
第二行包含 n 个整数,表示整个数列。
输出格式
输出一个整数,表示逆序对的个数。
数据范围
1 ≤ n ≤ 100000
题目大意
给定一个序列求出其中的逆序数对数量count,类似行列式的逆序数
样例
6
6 5 4 4 1 2
输出样例
13
算法思想
本题借鉴的是归并排序思想,在归并的时候对于满足逆序数的情况进行处理,计算出res的值(逆序对数)
-
首先对于数组进行划分区间[l,mid],[mid +1, r];
-
归并操作
1.对于逆序数组大致可以分为两种情况,第一种情况为逆序数对全部都在一边,也就是左边序列或者为右边序列,对于这种情况的处理可以直接按照直接计算可以获得
2.对于第二种情况也就是左边一个,右边一个,此时可以发现通过双指针算法,i和j指向的都是当前序列的最小值,故当出现q[i] > q[j]的情况时,那么i~mid的数都是应该大于q[j]的(因为是排好序的),那么对于q[j]的逆序数对数量应该是mid-i+1(也就是i到mid的区间长度),总的逆序数对就是这些q[j]的总和 -
扫尾操作
-
复制操作到tmp数组当中去
时间复杂度 $O(nlogn)$
参考文献
y总算法基础课
C++ 代码
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
int q[N],tmp[N];
LL res = 0;
void merge(int q[],int l,int r){
//递归边界 当只有一个数或者为0个数返回
if(l>=r) return ;
int mid = l+r >> 1;
//划分区间
merge(q,l,mid);
merge(q,mid+1,r);
//双指针,k存储的是tmp中已经拍好序的数量
int k=0,i=l,j=mid+1;
while(i<=mid && j<=r){
if(q[i] <= q[j]){
tmp[k++] = q[i++];
}else{
tmp[k++] = q[j++];
//计算q[j] j对应位置的逆序对数
res += mid - i+1;
}
}
//扫尾操作
while(i<=mid){
tmp[k++] = q[i++];
}
while(j<=r){
tmp[k++] = q[j++];
}
//复制操作,哪里来的回哪去
for(int i=l,j=0;i<=r;i++,j++){
q[i] = tmp[j]; //注意j无须++
}
}
int main(){
int n;
scanf("%d",&n);
for(int i = 0;i<n;i++){
scanf("%d",&q[i]);
}
merge(q,0,n-1);
cout << res << endl;
return 0;
}