题目描述
自己看哈
样例
自己看哈
算法1
逆序对数目
当执行合并操作时,设左、右子序列为A,B,当且仅当B中当前元素B[j]小于(而非小于等于,一定注意)A中当前元素A[i]时,出现逆序对。此时,A[i,…,r1]与B[j]构成r1-i+1个逆序对(r1为A右边界)。基于此原理递归求解即可得。唯一难度在于手动实现inplace_merge以及对逆序对的理解。还是那句老话,注意边界条件。
时间复杂度
和mergesort一样的O(nlogn)
C++ 代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<string>
using namespace std;
const int N = 1e5;
int q[N];
int p[N];
unsigned long _count=0;
void _merge(int q[], int l1, int r1, int l2, int r2);
void mergesort(int q[], int l, int r)
{
if (l == r)return;//递归基
int m = (r + l) >> 1;//选取中点为轴点
mergesort(q, l, m);
mergesort(q, m + 1, r);
_merge(q, l ,m, m + 1,r);
}
void _merge(int q[],int l1,int r1,int l2,int r2)
{
for (int i = l1; i <= r1; i++)
p[i] = q[i];//复制前半段
int i = l1, k = l1, j = l2;//前、主、后指针
while (i <= r1 || j <= r2)
{
if (i > r1)//前半段填充完毕
{
q[k++] = q[j++];
}
else if (j > r2)//后半段填充完毕
{
q[k++] = p[i++];
}
else
{
int j0 = j;
q[k++] = q[j] >= p[i] ? p[i++]: q[j++];
if(j-j0)
_count+=r1-i+1;//若有逆序对,则在此步骤j++,j0-j==1,可用用于判断是否发现逆序对
}
}
}
int main()
{
int n;
cin >> n;
int i = 0;
while (i != n)
{
cin >> q[i];
i++;
}
mergesort(q, 0, n - 1);
cout << _count;
}