P7514 [省选联考 2021 A/B 卷] 卡牌游戏 题解

思路

考虑枚举最小值。

首先按照 $a_i$ 从小到大给卡牌排序，然后枚举 $i$。

当 $a_i$ 作为最小值时，前 $i-1$ 个卡牌肯定要翻，然后如果还有多余次数就选择一段最长的 $a_i>b_i$ 的后缀，把这个后缀的卡牌全部反转后的卡牌就是 $a_i$ 作为最小值是的最优序列。

因为 $a_i$ 从小到大排序，所以有 $a_j(1 \le j < i)< a_i$，就不符合 $a_i$ 是最小值的条件，所以必须翻转。必须选择一段连续的 $a_i>b_i$ 的后缀翻转是因为如过不是连续的，假设最后没有翻转的卡牌是 $i$，则最大值一定 $\ge a_i$，那么所有在 $i$ 前的翻转是没有意义的。

当 $b_i$ 作为最小值时，和 $a_i$ 类似，二分找到 $j$ 使前 $j$ 个卡牌必须翻转，然后找一段最长的 $a_i>b_i$ 的后缀即可。

时间复杂度 $O(n \log n)$。

细节非常多，详见代码。

代码

#include<bits/stdc++.h>//包含常用头文件
using namespace std;//使用标准命名空间
typedef long long ll;//定义长整型别名
int n,m;//卡牌数量和最多翻面次数
struct N{//卡牌结构体
	int a,b;//正面和背面的数字
}a[1000010];//卡牌数组
bool cmp(N a,N b){//排序比较函数
	if(a.a!=b.a)return a.a<b.a;//首先按正面数字升序排序
	return a.b>b.b;//正面相同时按背面数字降序排序
}
int suf[1000010],smn[1000010],smx[1000010],pmn[1000010],pmx[1000010];//后缀和前缀的统计数组
int st[1000010][21],lg2[1000010];//ST表及预处理对数数组
inline int max(int a,int b){//自定义求最大值
	return a>b?a:b;
}
inline int min(int a,int b){//自定义求最小值
	return a<b?a:b;
}
int get(int l,int r){//ST表查询区间最大值
	if(l>r)return 0;//区间不合法返回0
	int d=lg2[r-l+1];//计算区间长度的对数
	return max(st[l][d],st[r-(1<<d)+1][d]);//返回两个子区间的最大值
}
int main(){
	ios::sync_with_stdio(0);//关闭同步流以加速输入输出
	cin.tie(0);//解除cin和cout的绑定
	cin>>n>>m;//读入卡牌数和翻面限制
	for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;//预处理以2为底的对数
	for(int i=1;i<=n;i++){
		cin>>a[i].a;//读入每张卡牌正面的数字
	}
	for(int i=1;i<=n;i++){
		cin>>a[i].b;//读入每张卡牌背面的数字
	}
	sort(a+1,a+1+n,cmp);//按照自定义规则对卡牌进行排序
	for(int i=1;i<=n;i++)st[i][0]=a[i].b;//初始化ST表的第0层为每张卡牌背面的数字
	for(int i=1;i<=20;i++){//构建ST表
		for(int x=1;x+(1<<i)-1<=n;x++){
			st[x][i]=st[x][i-1]>st[x+(1<<i-1)][i-1]?st[x][i-1]:st[x+(1<<i-1)][i-1];//状态转移
		}
	}
	smn[n+1]=1e9;//初始化后缀最小值为无穷大
	int ls=1;//未使用的变量
	for(int i=n;i;i--){//从后往前预处理后缀信息
		suf[i]=suf[i+1]+(a[i].a>a[i].b);//统计后缀中正面大于背面的卡牌数量
		smn[i]=min(smn[i+1],min(a[i].a,a[i].b));//维护后缀中min(a,b)的最小值
		smx[i]=max(smx[i+1],min(a[i].a,a[i].b));//维护后缀中min(a,b)的最大值
	}
	pmn[0]=1e9;//初始化前缀最小值为无穷大
	for(int i=1;i<=n;i++){//从前往后预处理前缀信息
		pmn[i]=min(pmn[i-1],a[i].b);//维护前缀中背面数字的最小值
		pmx[i]=max(pmx[i-1],a[i].b);//维护前缀中背面数字的最大值
	}
	int mx=0,la=0;//mx记录最大值，la记录相同正面数字的左边界
	int ans=1e9;//初始化答案为无穷大
	for(int i=1;i<=n;i++){//枚举每张卡牌作为最小值的情况
		if(a[i].a!=a[i-1].a)la=i;//更新相同正面数字的左边界
		if(pmn[la-1]>=a[i].a&&i-1<=m){ //情况1：当前卡牌正面数字作为最小值
			int now=m-(la-1);//计算剩余的翻面次数
			int l=i+1,r=n+1;
			while(l<r){//二分寻找可以翻转的后缀的左边界
				int mid=(l+r)>>1;
				if(suf[mid]<=now&&smn[mid]>=a[i].a)r=mid;//如果翻转次数足够且最小值合法，向左逼近
				else l=mid+1; 
			}
			ans=min(ans,max({pmx[la-1],smx[r],a[r-1].a})-a[i].a);//更新极差的最小值
		}
		int l=0,r=n;
		while(l<r){//情况2：当前卡牌背面数字作为最小值，二分寻找必须翻转的前缀右边界
			int mid=(l+r+1)>>1;
			if(a[mid].a<a[i].b)l=mid;//如果正面数字小于当前最小值，则必须翻转
			else r=mid-1;
		}
		if(pmn[r]<a[i].b||r>m)continue;//如果前缀背面最小值不合法或翻转次数超限，则跳过
		int now=m-r;//计算剩余的翻面次数
		int mx=(r>=i?max(get(1,i-1),get(i+1,r)):get(1,r));//计算前r张卡牌中未翻转卡牌的最大值
		l=r+1;r=n+1;
		while(l<r){//二分寻找可以翻转的后缀的左边界
			int mid=(l+r)>>1;
			if(suf[mid]<=now&&smn[mid]>=a[i].b&&suf[mid]-suf[mid+1])r=mid;//满足翻转条件且当前卡牌需要翻转
			else l=mid+1; 
		}
		mx=max(mx,max(smx[r],(r-1==i?a[r-2].a:a[r-1].a)));//计算整体最大值
		ans=min(ans,mx-a[i].b);//更新极差的最小值
	}
	cout<<ans;//输出最终的最小极差
	return 0;
}