更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19635009

大意

给出 $n$ 张卡牌，每张卡牌都有两个权值 $a_i$ 和 $b_i$，分别对应的是正面和反面，求在至少翻 $m$ 张牌，然后求出最小的极差。

思路

我们考虑这样的事，首先，我们不考虑每一张牌的情况，我们只考虑这个先处理极差的问题，我们先把这 $2n$ 张牌记录一下类型，然后将其排序。

排完序之后，我们需要的是选择一段区间 $[L, R]$，使得 $[L, R]$ 的区间包含所有的类型，且其中间反转的牌不超过 $m$ 个，那么这个区间的 $val_R - val_L$ 就是一个合法的答案，我们要想使得这个值尽可能的小，我们不妨使用双指针的写法，固定左端点，向右查询合法右端点。

这个过程是具有单调性的，你的 $L$ 向右，$R$ 也必定向右，具体过程是这样的，如果当前的区间不合法，那么就让 $R$ 右移，使其包含所有的 $n$ 个情况，一旦包含足够，就判断是否合法，这个过程是可以在扫描的过程中动态处理的，这步判断是 $\mathcal{O}(1)$ 的，如果是合法就将 $L$ 向右收缩，这样去看看有没有更优的 $val_R - val_L$。

代码

#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 1e6 + 5;
int n, m, l, r, cnt = 0;
struct node{
    long long val, id;
    bool op;
}k[MAXN << 1];
int t[MAXN << 1];
bool cmp(node x, node y){
    return x.val < y.val;
}

int main(){
    // freopen("card.in", "r", stdin);
    // freopen("card.out", "w", stdout);
    cin.tie(0) -> ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i ++){
        cin >> k[i].val;
        k[i].id = i;
        k[i].op = 1;
    }
    for(int i = 1;i <= n;i ++){
        cin >> k[i + n].val;
        k[i + n].id = i;
        k[i + n].op = 0;
    }
    sort(k + 1, k + 2 * n + 1, cmp);
//    for(int i = 1;i <= n * 2;i ++){
//        cout << k[i].val << ' ' << k[i].id << ' ' << k[i].op << '\n';
//    }
    for(l = 0;cnt + k[l + 1].op <= m && !t[k[l + 1].id];l ++){
        cnt += k[l + 1].op;
        t[k[l + 1].id] = 1;
    }
    for(r = 2 * n + 1;cnt + k[r - 1].op <= m && !t[k[r - 1].id];r --){
        cnt += k[r - 1].op;
        t[k[r - 1].id] = 1; 
    }
    long long ans = 1e9 + 7;
	while(l >= 0) {
		ans = min(k[r - 1].val - k[l + 1].val, ans);
		t[k[l].id] = 0;
		cnt -= k[l].op;
		l --;
        for(r;cnt + k[r - 1].op <= m && !t[k[r - 1].id];r --){
            cnt += k[r - 1].op;
            t[k[r - 1].id] = 1; 
        }
	}
	cout << ans << '\n';
}