欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

求逆序对(归并)

程序员文章站 2022-03-03 07:50:30
...

求逆序数对(归并解法)

简述

题目链接:https://www.luogu.com.cn/problem/P1908
这题主要是运用到逆序数排序是的数组有序性,那么逆序数对就是满足逆序数条件的那个数前面有多少个,然后全部加起来就可以了。

代码

#include <stdio.h>
#define ll long long int
#define maxn 500010
ll ans = 0;
ll temp[maxn] = { 0 }; //该数组用于Msort函数,保存临时结果
void Msort(ll *s, ll left, ll mid, ll right) { //该函数用于排序,主要是将一个数组看成两部分进行比较
	ll i = left, j = mid + 1, k = left;
	while (i <= mid && j <= right) { //该循环是归并排序关键部分,主要是两部分进行比较,小的放前面
		if (s[i] <= s[j]) {
			temp[k++] = s[i++];
		}
		else {
			ans += mid - i + 1; //这是用归并求逆序数最关键的一步,也就这一步
			temp[k++] = s[j++];
		}
	}
	while (i <= mid) { temp[k++] = s[i++]; } //两部分中有一部分没历遍完,就要用到这两个循环
	while (j <= right) { temp[k++] = s[j++]; }
	for (i = left; i <= right; i++) { //将最后结果放入原数组
		s[i] = temp[i];
	}
}
void Merge(ll *s, ll left, ll right) { //该函数用于数组拆分
	if (left >= right) { //结束条件
		return;
	}
	ll mid = (left + right) >> 1; //取中间值
	Merge(s, left, mid); //左半部
	Merge(s, mid + 1, right); //右半部
	Msort(s, left, mid, right); //调用Msort函数,进行排序
}
ll s[maxn] = { 0 };
int main() {
	ll t;
	while (~scanf("%lld", &t)) {
		while (t-- > 0) {
			ll n;
			scanf("%lld", &n);
			for (ll i = 1; i <= n; i++) {
				scanf("%lld", s + i);
			}
			ans = 0; //ans为全局变量,每次调用需要给它重新赋值
			Merge(s, 1, n);
			printf("%lld\n", ans);
		}
	}
	return 0;
}

解释

ans += mid - i + 1; //这是用归并求逆序数最关键的一步,也就这一步
比如 1 3 2
就会被拆成 1 3 为一对;2 为一对;然后再拆成1,3,2各为一队,之后在和;
先1和3比较,结果没变,所以ans没有变,然后就是1 3和2进行比较,其中 3 和 2满足逆序数条件,
就计算3那个位置前面有多少个数,所以答案为1;
可能不是清楚,有问题可以私聊我!