逆序数(归并排序)
逆序数
https://ac.nowcoder.com/acm/problem/15163
题目描述
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。比如一个序列为4 5 1 3 2， 那么这个序列的逆序数为7，逆序对分别为(4, 1), (4, 3), (4, 2), (5, 1), (5, 3), (5, 2),(3, 2)。
输入描述:
第一行有一个整数n(1 <= n <= 100000), 然后第二行跟着n个整数，对于第i个数a[i]，(0 <= a[i] <= 100000)。
输出描述:
输出这个序列中的逆序数
示例1
输入
5 4 5 1 3 2
输出
7
思路
在归并排序的基础上稍微修改即可
代码
//逆序数(归并排序)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n;
ll ans;//1e10
int a[N] , b[N];
void merge(int l , int r)
{
if(l >= r)
return ;
int mid = (l + r) >> 1;
merge(l , mid);
merge(mid + 1 , r);
int i = l , j = mid + 1 , k = l;
while(i <= mid && j <= r)
{
if(a[i] > a[j])
{
ans += mid - i + 1;
b[k++] = a[j++];
}
else
b[k++] = a[i++];
}
while(i <= mid)
b[k++] = a[i++];
while(j <= r)
b[k++] = a[j++];
for(int i = l ; i <= r ; i++)
a[i] = b[i];
}
int main()
{
scanf("%d" , &n);
for(int i = 0 ; i < n ; i++)
scanf("%d" , &a[i]);
merge(0 , n - 1);
printf("%lld\n" , ans);
return 0;
} 牛客算法竞赛入门课第二节习题题解 文章被收录于专栏
入门课第二节习题题解
查看14道真题和解析