省选联考 2021 A/B 卷 卡牌游戏 做题笔记

前言

非常有趣的一道双指针好题，前前后后思考了好几天并写了一天半，终于实现了题解大佬的线性做法，做完这道题也让我对双指针以及函数单调性有了更深的理解。目前已经在所有 oj 上都 AC 了，正确性应该是没有问题的。这篇做题笔记思路与该大佬的题解基本一致，在细节方面有一些补充。

思路

这道题的切入点就是观察最终序列的翻转方式。

性质 1

观察可得性质 1：

  • 最终序列被翻转的卡片一定是一段前缀和一段后缀。

证明 1

由于给出的 aa 是升序的，所以翻转中间的卡片要么对最小值和最大值无影响（因为中间的 aia_i 一定 ≥a1\geq a_1，≤an\leq a_n），要么会使最小值更小/使最大值更大，而我们要求的是最小极差，所以翻转中间的卡片没有意义。

思考怎么用这个性质去解题。

设已经翻转了长度为 ll 的一段前缀和长度为 rr 的一段后缀，可以定义如下变量：

  • lmaxl=max⁡{bi}(1≤i≤l)lmax_l=\max\{b_i\}(1\leq i\leq l)；
  • lminl=min⁡(min⁡{bi}(1≤i≤l),al+1)lmin_l =\min(\min\{b_i\}(1\leq i\leq l),a_{l+1})；
  • rmaxr=max⁡(max⁡{bi}(n−r+1≤i≤n),an−r)rmax_r=\max(\max\{b_i\}(n-r+1\leq i\leq n),a_{n-r})；
  • rminr=min⁡{bi}(n−r+1≤i≤n)rmin_r=\min\{b_i\}(n-r+1\leq i\leq n)。

此时序列的最小值为 min⁡(lminl,rminr)\min(lmin_l,rmin_r)，最大值为max⁡(lmaxl,rmaxr)\max(lmax_l,rmax_r)。

性质 2

下面切入性质 2：

  • lmaxlmax 和 lminlmin 单调不减，rmaxrmax 和 rminrmin 单调不增。

证明 2

lmaxlmax 和 rminrmin 显然单调，但剩下两个量并不单调。
现在就到了这个做法的精妙之处：我们可以对 lminlmin 和 rminrmin 进行一些处理，使它们变得单调，这样就方便用二分或者双指针之类对单调性有要求的算法来解题；而这个处理就是对 lminlmin 取前缀最大值，对 rmaxrmax 取前缀最小值。

假设存在一个位置 l′l'，满足 l′<ll'<l 且 lminl′>lminllmin_{l'}>lmin_l。
因为 lmaxlmax 单调不减，所以 lmaxl′≤lmaxllmax_{l'}\leq lmax_l，
故此时在左边翻转 l′l' 个数一定比翻转 ll 个更优。
同时由于 l′<ll'<l，满足 l+r≤ml+r\leq m 的 rr 也可以用在 l′l' 上，所以对 lminlmin 取前缀最大值既满足最优性，又满足合法性。
对 rmaxrmax 的证明同理。

处理完之后就可以直接开始通过双指针解题。
考虑枚举 l,rl,r 和当前的最小值，于是我们需要枚举两次，第一次枚举 ll 并将 lminllmin_l 作为当前最小值，第二次枚举 rr 并将 rminrrmin_r 作为当前最小值，这样可以确保不重不漏。在枚举 ll 的过程中，我们的目标就是找到最大并满足 rminr≥lminlrmin_r\geq lmin_l 和 l+r≤ml+r\leq m 的 rr（因为 rmaxrmax 单调不增，所以rmaxrmax 也一定最小）来更新答案，而枚举 rr 时要找的就是满足条件的最小的 ll。

关于枚举顺序的问题，以 ll 为例：ll 减小时，lminllmin_l 减小，因为 rminr≥lminlrmin_r\geq lmin_l 所以 rminrrmin_r 可以适当减小，rr 可以适当增大，于是 rmaxrmax 减小，就取到了对当前 ll 最优的 rr，所以 ll 要倒序枚举，如果正序枚举，则最后 rmaxrmax 会变大，取到的解就不是最优的。rr 的枚举顺序同理可证。

现在这题我们就做完了，代码很短也很好写，但是细节非常多。一定要在各个 oj 上都交一遍，因为这题能卡掉错解的数据貌似不是很好构造。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int a[N],b[N],lmax[N],lmin[N],rmax[N],rmin[N],n,m;
void solve(){
    read(n);read(m);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++) read(b[i]);
    lmin[0] = rmin[0] = inf;
    for(int i=1;i<n;i++){
    lmin[i] = min(lmin[i-1],b[i]);
    lmax[i] = max(lmax[i-1],b[i]);
    rmin[i] = min(rmin[i-1],b[n-i+1]);
    rmax[i] = max(rmax[i-1],b[n-i+1]);
    }
    for(int i=0;i<n;i++){
        lmin[i] = min(lmin[i],a[i+1]);
        rmax[i] = max(rmax[i],a[n-i]);
        if(i>0){
        lmin[i] = max(lmin[i],lmin[i-1]);
        rmax[i] = min(rmax[i],rmax[i-1]);
        }
    }
    int ans = inf;
    for(int l=m,r=0;l>=0;l--){ //取lmin[l]为最小值
        while(lmin[l]<=rmin[r+1] && l+r<m) r++;
        while(l+r>m && r) r--;
        if(lmin[l]>rmin[r]) continue;
        int nowmax = max(lmax[l],rmax[r]);
        ans = min(ans,nowmax-lmin[l]);
    }
    for(int r=1,l=m-1;r<=m;r++){ //取rmin[r]为最小值
        while(l>0 && rmin[r]<=lmin[l-1] || l+r>m) l--;
        if(rmin[r]>lmin[l]) continue;
        int nowmax = max(lmax[l],rmax[r]);
        ans = min(ans,nowmax-rmin[r]);
    }
    cout<<ans;
}