P7514 [省选联考 2021 A/B 卷] 卡牌游戏
大意
给出 \(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';
}