- 火柴排队
505. 火柴排队 - AcWing题库 |
---|
难度:中等 |
时/空限制:1s / 128MB |
总通过数:2058 |
总尝试数:4484 |
来源:NOIP2013提高组 |
算法标签 贪心离散化树状数组归并排序 |
题目内容
涵涵有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度。
现在将每盒中的火柴各自排成一列,同一列火柴的高度互不相同,两列火柴之间的距离定义为:
∑
i
=
1
n
=
(
a
i
−
b
i
)
2
\sum_{i=1}^{n}=(a_{i}-b_{i})^2
i=1∑n=(ai−bi)2
其中
a
i
a_{i}
ai 表示第一列火柴中第i个火柴的高度,
b
i
b_{i}
bi 表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。
请问得到这个最小的距离,最少需要交换多少次?
如果这个数字太大,请输出这个最小交换次数对 99,999,997 取模的结果。
输入格式
共三行,
第一行包含一个整数 n,表示每盒中火柴的数目。
第二行有 n 个整数,每两个整数之间用一个空格隔开,表示第一列火柴的高度。
第三行有 n 个整数,每两个整数之间用一个空格隔开,表示第二列火柴的高度。
输出格式
输出共一行,包含一个整数,表示最少交换次数对99,999,997取模的结果。
数据范围
1
≤
n
≤
1
0
5
1\le n\le 10^5
1≤n≤105,
0
≤
火柴高度
≤
2
31
−
1
0\le火柴高度\le 2^{31}-1
0≤火柴高度≤231−1
输入样例:
4
2 3 1 4
3 2 1 4
输出样例:
1
题目解析
- 有两盒火柴,每盒有n根,每根火柴都有一个高度
- 每一盒火柴内的高度各不相同
- 把两盒火柴排成一行,
第一盒火柴用a来表示 a 1 , a 2 … a n a_{1},a_{2}\dots a_{n} a1,a2…an
第二盒火柴用b来表示 b 1 , b 2 … b n b_{1},b_{2}\dots b_{n} b1,b2…bn
所有的a都是互不相同的,所有的b也都是互不相同的 - 可以将所有相邻的火柴交换位置,两行火柴都可以交换
- 计算一下所有对应位置差的平方和,要让平方和最小的话,最少需要交换多少次
如果数字太大,输出次数对99999997取模的结果
数据范围是
1
0
5
10^5
105,所以时间复杂度需要控制在
O
(
n
log
n
)
O(n\log n)
O(nlogn)
考虑两个问题
- 什么情况下可以使和最小
- 如何通过最少的交换次数得到和最小的情况
问题一
不需要考虑顺序
距离只跟每两根火柴的对应关系有关
至于每根火柴在序列中的哪个位置是没有关系的因此只需要考虑 a 1 a_{1} a1应该对应谁, a 2 a_{2} a2应该对应谁,以此类推
为了方便将a序列排序,因为a是不用考虑顺序的,第一问不需要考虑顺序
排成从小到大的结果
b也是升序排列的时候,平方和最小
再判断最小的数在最好的情况下应该对应哪个b,第二小的数应该对应哪个b,以此类推
可以猜一下,当b也是升序排列的时候,平方和最小
类似于排序不等式,但形式不完全一样
证明方式和排序不等式一样,和排队打水一样
913.排队打水
用反证法证明,假设b不是升序
必然存在
b
i
>
b
i
+
1
b_{i}>b_{i+1}
bi>bi+1,而
a
i
<
a
i
+
1
a_{i}<a_{i+1}
ai<ai+1
尝试交换这两个数
a
i
<
a
i
+
1
a_{i}<a_{i+1}
ai<ai+1
交换前
b
i
>
b
i
+
1
b_{i}>b_{i+1}
bi>bi+1
交换后
b
i
+
1
<
b
i
b_{i+1}<b_{i}
bi+1<bi
交换前后只影响
a
i
和
a
i
+
1
a_{i}和a_{i+1}
ai和ai+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
=(a_{i}-b_{i})^2+(a_{i+1}-b_{i+1})^2-(a_{i}-b_{i+1})^2-(a_{i+1}-b_{i})^2
=(ai−bi)2+(ai+1−bi+1)2−(ai−bi+1)2−(ai+1−bi)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
)
=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})
=2(−aibi−ai+1bi+1+aibi+1+ai+1bi)=2(ai−ai+1)(bi+1−bi)
最终的结果大于零,所以①大于②
所以交换前的总和大于交换后的总和
因此可以发现,如果存在一对逆序的话,(b如果不是升序,一定存在相邻的逆序),交换一下总和会变小,说明不是升序的话,就一定不是最优解
所以第一个问题,最小的a一定对应最小的b,第二小的a一定对应第二小的b,以此类推
问题二
需要考虑顺序
第二问就不能排序了,因为它只能交换相邻的火柴
比如
A 3 1 4 5 2
B 2 5 4 1 3
第一问不是真的排序,这是考虑a里面最小的1,在最优解里面应该对应哪个b
每个数的范围比较大,在
0
…
2
31
−
1
0\dots2^{31}-1
0…231−1以内
后面因为要用这个数值当下标,数值比较大的话不容易做
但是这个问题是和这些数的绝对值是没有关系的,只和每个数的相对大小有关系,我们要把b调整成和a相对大小一样的序列,绝对值是没有影响的
离散化
做一个离散化,将序列映射成从1到n或者从0到n-1的连续自然数,这样做的好处是可以将值域可以从所有整数范围变到n以内
2.1 ∗ 1 0 9 → 1 0 5 2.1*10^{9}\to 10^5 2.1∗109→105,这样就可以使用数组存了离散化
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 ) O(n\log n) O(nlogn)
788.逆序对的数量 -
树状数组 O ( n log n ) O(n\log n) O(nlogn)
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 < ⋯ < a p n a_{p_{1}}<a_{p_{2}}<\dots<a_{p_{n}} ap1<ap2<⋯<apn
p 1 p_{1} p1存的是a里面最小的一个数的下标, p 2 p_{2} p2存的是第二小的数的下标 -
二分的写法
- 二分可以自己写
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;
}
- 考虑一下怎么统计逆序数对
merge_sort()函数中,左右两边归并
b[j]<b[i]
的话,前半段所有大于b[j]
的数应该是从i到mid
i前面的都是小于b[j]
的
i后面的都是大于b[j]
的
所以整个区间里面,前半段大于b[j]
的数量,就是i~mid