题目概述
Alice 有 \(n\) 张卡牌，第 \(i\)（\(1 \le i \le n\)）张卡牌的正面有数字 \(a_i\)，背面有数字 \(b_i\)，初始时所有卡牌正面朝上。
现在 Alice 可以将不超过 \(m\) 张卡牌翻面，即由正面朝上改为背面朝上。Alice 的目标是让最终朝上的 \(n\) 个数字的极差（最大值与最小值的差）尽量小。请你帮 Alice 算一算极差的最小值是多少。、
分析
经典的做法，套路的做法：二分极值然后进行check，不难发现我们直接枚举最小值，最大值也就知道了，然后他可以框住一个区间，这个区间随着最小值增大是往右动的，然后记录前后缀最大最小值就行了。
代码
时间复杂度 \(\mathcal{O}(n\log V)\)，一开始写了一个 set 的，直接T飞了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <set>
#define int long long
#define N 1000006
using namespace std;
int n,m;
struct node{int a,b;
}da[N];
vector<int> ls;
int Lmin[N],Lmax[N],Rmin[N],Rmax[N];
bool check(int k) {int j = 1,nxt = 1;for (int i = 0;i < ls.size();i ++) {int mn = ls[i];int mx = mn + k;bool flag = 0;while(nxt <= n && da[nxt].a <= mx) nxt ++;while(j <= n && da[j].a < mn) {if (da[j].b < mn) return false;j ++;}if (Lmin[j - 1] < mn) return false;if (Lmax[j - 1] > mx || Rmin[nxt] < mn || Rmax[nxt] > mx) continue;if (n - nxt + j <= m) return true;}return false;
}
signed main(){cin >> n >> m;for (int i = 1;i <= n;i ++) scanf("%lld",&da[i].a),ls.push_back(da[i].a);for (int i = 1;i <= n;i ++) scanf("%lld",&da[i].b),ls.push_back(da[i].b);stable_sort(ls.begin(),ls.end());ls.erase(unique(ls.begin(),ls.end()),ls.end());stable_sort(da + 1,da + 1 + n,[](node x,node y) {return x.a < y.a;});Lmin[0] = 1e18;for (int i = 1;i <= n;i ++) Lmin[i] = min(Lmin[i - 1],da[i].b),Lmax[i] = max(Lmax[i - 1],da[i].b);Rmin[n + 1] = 1e18;for (int i = n;i;i --) Rmin[i] = min(Rmin[i + 1],da[i].b),Rmax[i] = max(Rmax[i + 1],da[i].b);int l = 0,r = ls.back() - *ls.begin(),res = r;while(l <= r) {int mid = l + r >> 1;if (check(mid)) r = mid - 1,res = mid;else l = mid + 1;}cout << res;return 0;
}