【AcWing】蓝桥杯集训每日一题Day5|归并排序|离散化|二分|逆序数对|505.火柴排队(C++)

火柴排队

505. 火柴排队 - AcWing题库
难度：中等
时/空限制：1s / 128MB
总通过数：2058
总尝试数：4484
来源：NOIP2013提高组
算法标签贪心离散化树状数组归并排序

题目内容

涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。
现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：
$\sum_{i=1}^{n}=(a_{i}-b_{i})^2$
其中 $a_{i}$ 表示第一列火柴中第i个火柴的高度， $b_{i}$ 表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。
请问得到这个最小的距离，最少需要交换多少次？
如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。

输入格式

共三行，
第一行包含一个整数 n，表示每盒中火柴的数目。
第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。
第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

输出格式

输出共一行，包含一个整数，表示最少交换次数对99,999,997取模的结果。

数据范围

$1\le n\le 10^5$ ,
$0\le火柴高度\le 2^{31}-1$

输入样例：

4
2 3 1 4
3 2 1 4

输出样例：

题目解析

有两盒火柴，每盒有n根，每根火柴都有一个高度
每一盒火柴内的高度各不相同
把两盒火柴排成一行，
第一盒火柴用a来表示 $a_{1},a_{2}\dots a_{n}$
第二盒火柴用b来表示 $b_{1},b_{2}\dots b_{n}$
所有的a都是互不相同的，所有的b也都是互不相同的
可以将所有相邻的火柴交换位置，两行火柴都可以交换
计算一下所有对应位置差的平方和，要让平方和最小的话，最少需要交换多少次

如果数字太大，输出次数对99999997取模的结果
数据范围是 $10^5$ ，所以时间复杂度需要控制在 $O(n\log n)$

考虑两个问题

什么情况下可以使和最小
如何通过最少的交换次数得到和最小的情况

问题一

不需要考虑顺序

距离只跟每两根火柴的对应关系有关
至于每根火柴在序列中的哪个位置是没有关系的

因此只需要考虑 $a_{1}$ 应该对应谁， $a_{2}$ 应该对应谁，以此类推
为了方便将a序列排序，因为a是不用考虑顺序的，第一问不需要考虑顺序
排成从小到大的结果

b也是升序排列的时候，平方和最小

再判断最小的数在最好的情况下应该对应哪个b，第二小的数应该对应哪个b，以此类推

可以猜一下，当b也是升序排列的时候，平方和最小
类似于排序不等式，但形式不完全一样
证明方式和排序不等式一样，和排队打水一样
913.排队打水

用反证法证明，假设b不是升序
必然存在 $b_{i}>b_{i+1}$ ，而 $a_{i}<a_{i+1}$
尝试交换这两个数
$a_{i}<a_{i+1}$
交换前 $b_{i}>b_{i+1}$
交换后 $b_{i+1}<b_{i}$

交换前后只影响 $a_{i}和a_{i+1}$ 这两列，不影响其他的列，所以其他列的和都是不变的
所以考虑交换前交换后的平方和的差异的话，只需要考虑这两列的差异就可以了

交换前的总和设为①，交换后的总和设②
比较关系可以做差，通过计算①-②，比较大小关系
①-② $a_{i}-b_{i})^2+(a_{i+1}-b_{i+1})^2-(a_{i}-b_{i+1})^2-(a_{i+1}-b_{i})^2$
$2(-a_{i}b_{i}-a_{i+1}b_{i+1}+a_{i}b_{i+1}+a_{i+1}b_{i})=2(a_{i}-a_{i+1})(b_{i+1}-b_{i})$
最终的结果大于零，所以①大于②

所以交换前的总和大于交换后的总和
因此可以发现，如果存在一对逆序的话，(b如果不是升序，一定存在相邻的逆序)，交换一下总和会变小，说明不是升序的话，就一定不是最优解

所以第一个问题，最小的a一定对应最小的b，第二小的a一定对应第二小的b，以此类推

问题二

需要考虑顺序

第二问就不能排序了，因为它只能交换相邻的火柴
比如
A 3 1 4 5 2
B 2 5 4 1 3
第一问不是真的排序，这是考虑a里面最小的1，在最优解里面应该对应哪个b

每个数的范围比较大，在 $0\dots2^{31}-1$ 以内
后面因为要用这个数值当下标，数值比较大的话不容易做
但是这个问题是和这些数的绝对值是没有关系的，只和每个数的相对大小有关系，我们要把b调整成和a相对大小一样的序列，绝对值是没有影响的

离散化

做一个离散化，将序列映射成从1到n或者从0到n-1的连续自然数，这样做的好处是可以将值域可以从所有整数范围变到n以内
$2.1*10^{9}\to 10^5$ ，这样就可以使用数组存了

离散化
802.区间和

离散化完之后，a数组变为1-n，b数组也变为1-n，
接下来要把a当中的1对应b当中的1，a当中的2对应b当中的2，以此类推
每次只能交换a当中相邻的两个数或者b里面相邻的两个数

考虑简化问题

假设输入的a是有序的
A 1 2 3 4 5
B 2 1 5 3 4
假设只能交换B
如果把b变成和a一样的大小关系，a是升序的，所以要把b变成升序，最少需要交换几次

变成一个经典问题

给一个排列，问我们最少交换几次，每次交换相邻元素，把它变成一个升序
答案：逆序对数
看一下所有的元素对，不一定相邻，有多少个前一个大于后一个

为什么交换最少次数是逆序对

如果有序的话，逆序对应该是0
初始的时候，求一个逆序对，

2，1、
5，3、
5，4，

总共三个逆序对，每次交换两个相邻元素
比如交换x，y，每次交换xy之后对于逆序对的影响，如果逆序对数是k的话，只能让k+1或者-1，
如果x小于y的话，交换完，k+1
如果x大于y的话，交换完，k-1
交换xy的话，它不影响y跟前面的数的关系，也不影响x跟后面的数的关系，所以只会影响x跟y的关系，所以只会对逆序对数产生1的影响，要么+1，要么-1
最终要使逆序对变成零，所以最少需要操作3次
如果初始有k个逆序对的话，说明最少需要操作k次
所以答案一定大于等于k

可以等于k吗

可以，如果序列不是升序的话，必然存在一对相邻元素x，y，使得x大于y，交换这个相邻的逆序对就可以了，交换一次，k-1
因此只要k大于0，就必然可以找到一对相邻的前一个大于后一个，可以交换，必然可以使k-1
这样就可以构造一种方案，使得恰好操作k次，使得k变为0
所以等号可以取到

冒泡排序，每次交换就是会交换一对相邻的逆序对，冒泡排序就是一种方案

比如：2 1 5 3 4
由于不是升序，必然存在一对相邻的，前一个大于后一个
交换：1 2 5 3 4
5 3是一个
交换： 1 2 3 5 4
5 4是一个
交换： 1 2 3 4 5
三次

所以如果逆序对数是k的话，说明最少交换次数就是k

如何求逆序对数

经典问题

归并排序，递归的做法 $O(n\log n)$
788.逆序对的数量
树状数组 $O(n\log n)$
241.楼兰图腾
如果不止可以交换b，还可以交换a的话
最优解是：
因为a数组是升序的，逆序对数是0，b数组是k，
不管交换a还是交换b，如果交换a的话，相当于是把a的逆序对数+1或者-1，交换b的话，相当于是把b的逆序对数+1或者-1.
不管交换a还是交换b，a和b逆序对的差值，最多只能-1
初始的时候逆序对的差值是k，所以最少需要操作k次，所以也是大于等于k
所以如果不仅可以操作b，还可以操作a的话，跟只可以操作b是一样的
如果a没有序的话
可以用映射的思想，因为a和b已经离散化了，它就是一个1~n的排列
把a里面第一个数映射到1，把第二个数映射到2，以此类推，把a和b都映射一遍就好了

A 3 1 4 5 2
  1 2 3 4 5
B 2 5 4 1 3
  5 4 3 2 1

映射完之后，a就变成升序了，就变成了之前简化的问题
答案就是此时b序列当中的逆序对数

映射完之后把b变成升序，等价于把b映射之后的结果变成了1 2 3 4 5
这样a和b映射之后的结果都是1 2 3 4 5
根据映射可以反推回去，就直到交换完之后，原来的值
A 3 1 4 5 2
B 3 1 4 5 2
所以映射回去，就和原问题是一样的

a和b中的元素一定是一样的
因为离散化过
离散化之后，a和b都会变成1~n

为什么可以离散化
因为这个题只考虑相对关系，不考虑绝对关系

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, MOD = 99999997;

int n;
int a[N], b[N], c[N], p[N];
//c存映射之后的数组,p是用来离散化的

void work(int a[])
{
	//把下标存下来，排下标就可以了
	for (int i = 1; i <= n; i ++)
		p[i] = i;
	//把p当作下标，根据下标在a当中对应的值来排
	sort (p + 1, p + n + 1, [&](int x, int y)
	{
		return a[x] < a[y];
	});
	//p就是下标，排完之后满足p有序，p作为下标的话，在a中有序

	//把a映射一下
	for (int i = 1; i <= n; i ++)
		a[p[i]] = i;
	//把a当中第二小的数映射到i
}

int merge_sort(int l, int r)
{
	if (l >= r)  //如果区间里只有一个数的话，就是0
		return 0;
	int mid = l + r >> 1;  //求一下中点
	//求一下左右两边的逆序对的总和
	int res = (merge_sort(1, mid) + merge_sort(mid + 1, r)) % MOD;
	//二类归并一下
	int i = 1, j = mid + 1, k = 0;
	while (i <= mid && j <= r)
	{
		if (b[i] < b[j])
			p[k ++] = b[j ++];
		else
			p[k ++] = b[j ++];
			res = (res + mid - i + 1) % MOD;
	}
	//把左边没有归并完的归并完
	while (i <= mid)
		p[k ++] = b[i ++];
	//把右边没有归并完的归并完
	while (j <= r)
		p[k ++] = b[j ++];
	//把临时数组中的元素存回原数组
	for (i = l, j = 0; j < k; i++, j++)
		b[i] = p[j];
	return res;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++)
		scanf("%d", &a[i]);
	for (int i = 1; i <= n; i ++)
		scanf("%d", &b[i]);
	
	//先离散化一下
	work(a), work(b);

	//求一下c数组的映射
	for (int i = 1; i <= n; i ++)
		c[a[i]] = i;  //c当中第i个数，映射到i
	for (int i = 1; i <= n; i ++)
		b[i] = c[b[i]];  //要查一下b的数值映射的结果是什么

	//求一下b的逆序对数
	printf ("%d\n", merge_sort(1, n));
	return 0;
}

其中work函数里离散化p排序的时候
排完之后
$a_{p_{1}}<a_{p_{2}}<\dots<a_{p_{n}}$
$p_{1}$ 存的是a里面最小的一个数的下标， $p_{2}$ 存的是第二小的数的下标
二分的写法
1. 二分可以自己写

int find (int x)
{
	//在p这个升序里边，二分出来a第一次出现的位置
	int l = 1, r = n;
	while (l < r)
	{
		int mid = l + r >> 1;
		if (p[mid] >= x) r = mid;
		else l = mid + 1;
	}
	return r;
}

void work(int a[])
{
	//首先把a当中的数都存下来
	for (int i = 1; i <= n; i ++)
		p[i] = a[i];
	//把p排个序
	sort (p + 1, p + n + 1);
	//二分
	for (int i = 1; i <= n; i ++)
		a[i] = find (a[i]);
}

2. 或者使用库函数

void work(int a[])
{
	//首先把a当中的数都存下来
	for (int i = 1; i <= n; i ++)
		p[i] = a[i];
	//把p排个序
	sort (p + 1, p + n + 1);
	//二分
	for (int i = 1; i <= n; i ++)
		a[i] = lower_bound(p + 1, p + n + 1, a[i]) - p;
}