归并排序求逆序数 牛客网

缘起

【1】中我们已经给出了使用树状数组+离散化来求一个序列的逆序数的O(nlogn)算法. 这里给出使用归并排序的过程中完成逆序数的求解. 题目链接依旧是

传送门

分析

没什么好说的，归并即分治算法, 所以我们要考虑的核心问题就是知道了一个数组的左半边的逆序数和一个数组的右半边的逆序数之后，归并过程中怎么求出原数组的逆序数. 此题唯一需要注意的是对于10w规模的数组, 它的逆序数完全可能是O（n^2）的，达到100亿, 所以需要使用long long 来表示逆序数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <algorithm>
using namespace std;
//#define LOCAL
const int MAX_N = 100000+5;
typedef long long LL;
int a[MAX_N], n, tmp[MAX_N];

LL merge(int *a, int lb, int ub) // 求a[lb,ub]的逆序数
{
	if (lb>=ub) return 0;
	int mid = (lb+ub)>>1, i, j, k;
	LL l = merge(a,lb,mid); // 注意，为了防止溢出，一定要用LL
	LL r = merge(a, mid+1, ub);
	LL cnt = 0; // 分别求出 a[lb,mid]和a[mid+1, ub]的逆序数, cnt是归并过程中产生的逆序数
	for (i = 0; i<mid-lb+1; tmp[i] = a[i+lb],i++);
	i=0, j=mid+1, k=lb;
	while(i<=mid-lb && j<=ub)
	{
		if (tmp[i]<=a[j]) // 归并是稳定算法, 所以要 <= 而不是 <
		{
			a[k++] = tmp[i++];
		}
		else
		{
			a[k++] = a[j++];
			cnt += (j-k); // 这就是核心, 因为 拿  145和 238 两个有序序列归并举例, 归并之后是 123458, 归并的过程中发现2原本应该排在索引（k=）1（从0开始），但是在原先的序列145238中排在(j=)3，所以有(j-k)1个不应该排在它前面（这个数字就是4），就是j-k的值
		}
	}
	while(i<=mid-lb)
	{
		a[k++] = tmp[i++];
	}
	while(j<=ub)
	{
		a[k++]=a[j++];
	}
	return l+r+cnt;
}




int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out","w", stdout);
#endif
	scanf("%d", &n);
	for (int i = 0; i<n;scanf("%d", a+i),i++);
	printf("%lld\n", merge(a,0,n-1));
#ifdef LOCAL
	fclose(stdin);
#endif
	return 0;
}

ac情况

通过

您的代码已保存
答案正确:恭喜！您提交的程序通过了所有的测试用例

参考

【1】https://yfsyfs.github.io/2019/06/06/%E7%A6%BB%E6%95%A3%E5%8C%96-%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84-%E6%B1%82%E9%80%86%E5%BA%8F%E6%95%B0/