洛谷 P1966 火柴排队 题解

归并排序

很玄学的一道题目，用另类的方法求出逆序对的数量就可以AC

我的思路是这样的：

按照题目，输入数据用两个数组a,b储存，

同时，用另外两个数组c,d分别对应前面两个a,b储存，

就是前面两个的复制

然后在将复制出来的拍一下序，

用另一个类似桶的分别记录在a,b两个数组的数字里面，

某一个数是里面第几大的数

然后按照b里面的顺序，也就是里面的从第一个到最后一个的数在桶里面对应的

是第几个

给a标一下第一第二

比如b中的顺序是 ：1 ， 3 ， 2 ， 4

在a中的顺序是 ：1 ， 4 ， 2 ， 3

那么根据b的来看，1在b中是第一个所以a中的1对应的还是1

3在b中是第二个，所以a中3对应的是2

.....

这样弄完之后

a成了1 , 4 , 3 , 2

然后归并排序

这里为什么可以用归并排序呢？

归并排序板子是按照大小来排序的，这里却是将a按照b来排序的

所以b就可以看作是大小，是将a在b中的位置看做是大小，这样归并排序按照改

完后的大小排一下

同时记录逆序对，也就是每一个需要挪动的次数

记录和，这个和就是需要挪动的次数的总和

完整代码

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int Max = 100005;

const int mo = 99999997;//注意必须要mo一旦忽视就会错掉两个点

int a[Max],b[Max];

int c[Max],d[Max];

int num1[Max],num2[Max];

int js[Max];

long long ans = 0;

int aa[Max];

void gui(int x,int y)//归并排序板子

{

	if(x == y)return;

	int mid = (x + y) >> 1;

	gui(x,mid);gui(mid + 1,y);

	int i = x,j = mid + 1;

	int k = x;

	while(i <= mid && j <= y)

	{

		if(a[i] <= a[j])aa[k ++] = a[i ++];

		else	aa[k ++] = a[j ++],ans += mid - i + 1,ans %= mo;;

	}

	while(i <= mid)

		aa[k ++] = a[i ++];

	while(j <= y)

		aa[k ++] = a[j ++];

	for(int i = x;i <= y;++ i)

		a[i] = aa[i];

}

int main()

{

	int n;

	scanf("%d",&n);

	for(int i = 1;i <= n;++ i)scanf("%d",&a[i]),c[i] = a[i];

	for(int i = 1;i <= n;++ i)scanf("%d",&b[i]),d[i] = b[i];//输入数据

	sort(d + 1,d + 1 + n);

	for(int i = 1;i <= n;++ i)

		num1[d[i]] = i;

	sort(c + 1,c + 1 + n);

	for(int i = 1;i <= n;++ i)

		num2[c[i]] = i;

	for(int i = 1;i <= n;++ i)

		js[num1[b[i]]] = i;

	for(int i = 1;i <= n;++ i)

		a[i] = js[num2[a[i]]];//前面这一大坨都是预处理下标

	gui(1,n);

	cout << ans % mo <<endl;

	return 0;

}