当前位置:首页 > 单调队列 > 尺取法 > 正文
洛谷P7514[省选联考2021AB卷]卡牌游戏
940+

题目大意:n张卡牌,每张有两面,正面是$a_i$,反面是$b_i$,一开始正面朝上排好序,现在可以翻过来m张,请问朝上的数字最大值减最小值之差最小是多少?

题目描述

Alice 有 $n$ 张卡牌,第 $i$($1 \le i \le n$)张卡牌的正面有数字 $a_i$,背面有数字 $b_i$,初始时所有卡牌正面朝上。

现在 Alice 可以将不超过 $m$ 张卡牌翻面,即由正面朝上改为背面朝上。Alice 的目标是让最终朝上的 $n$ 个数字的极差(最大值与最小值的差)尽量小。请你帮 Alice 算一算极差的最小值是多少。

输入输出格式

输入格式

第一行,两个正整数 $n, m$,代表卡牌张数与至多翻面张数。
第二行,$n$ 个正整数,第 $i$ 个数字表示 $a_i$。
第三行,$n$ 个正整数,第 $i$ 个数字表示 $b_i$。数据保证卡牌上的 $2 n$ 个数字互不相同,且卡牌按照 $a_i$ 升序给出。

输出格式

仅一行,一个整数,表示答案。

输入输出样例

输入样例 #1

6 3
8 11 13 14 16 19
10 18 2 3 6 7

输出样例 #1

8

输入样例 #2

见附件中的 card/card2.in。

输出样例 #2

见附件中的 card/card2.ans。

输入样例 #3

见附件中的 card/card3.in。

输出样例 #3

见附件中的 card/card3.ans。

说明

**【样例 #1 解释】**

最优方案之一:将第 $1, 5, 6$ 张卡牌翻面,最终朝上的数字依次为 $10, 11, 13, 14, 6, 7$,极差为 $14 – 6 = 8$。

**【数据范围】**

对于所有测试数据:$3 \le n \le {10}^6$,$1 \le m < n$,$1 \le a_i, b_i \le {10}^9$。

每个测试点的具体限制见下表:

测试点编号 特殊限制

解题思路

显然,要翻就翻两边的,而且是连续的。左边翻的目的是,让左边最小的尽量大一点;右边翻的目的是,让右边最大的尽量小一点。因为原来的a序列是递增的,差值为$a_r – a_l$,我们希望大的尽量小,小的尽量大,差值才会缩小。如果左边翻出更小,之后没必要再翻,怎么翻最小也不会变大了。右边也一样道理。

首先,我们可以预处理出b序列的前缀最小值x、前缀最大值y、后缀最小值X、后缀最大值Y。

接着,枚举左端点,然后找右端点。左边最多翻m张牌,这m张牌必须保证翻了变大,即$b_i > a_i$,而且翻了是有作用的,不会比前面最小值小,即$b_i > x[i-1]$,如果没用,后面翻过来最小值不变大,留给右边翻效果更好。

右端点只需要一直往左走就行,如何保证指针不回退?必翻才翻!

所选区间为[l, r],左边端点l往左移动,最小值不递增,只要右边端点r翻过来后,不影响最大值和最小值,肯定翻过来。不影响最大值,是指能让右边最大值变小(或不变大),即$b_r < a_r$,能翻就翻,反正不影响左边翻的次数。不影响最小值,是指翻过来后,不出现最小值,这样,下一次l往左移动,也必然翻他!

如果影响最小值,就不翻吗?也有可能最好吧?是的!有可能翻了更好!那么,只要他比上一张牌大($b_r > a_{l-1}$),也翻!因为下次l-1不翻的时候,必然翻他,之后对l-1的枚举,也不遗漏最好的右端点。如果比上一张牌$a_{l-1}$小,上一张牌没必要翻,等不翻他的时候在想要不要翻r吧。

这样,所有的左端点l,都能与其最优的右端点r尝试匹配,我们只需打擂台找最优值即可。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,,

洛谷P7514[省选联考2021AB卷]卡牌游戏:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!