如何通过卡牌游戏策略在P7514比赛中脱颖而出？
摘要：P7514 [省选联考 2021 AB 卷] 卡牌游戏 大意 给出 (n) 张卡牌，每张卡牌都有两个权值 (a_i) 和 (b_i)，分别对应的是正面和反面，求在至少翻 (m) 张牌，然后求出最小的极差。 思路 我们考虑这
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';
}