CF2113D Cheater 题解

如果想要真正靠推导做出这道题，那么还是不容易的。

下面我就来推导一下这道题的完整思路。

我们肯定想把玩牌的过程转移到数列上：有两个指针

i

和

j

，初始均为

1

。比较

a_i

和

b_j

的大小，如果

a_i>b_j

，那么

i

向右移，玩家得一分。否则

j

向右移，庄家得一分。

提示一：每一轮输掉的牌的值有什么变化？

首先我们能发现一个性质：我们令本次输掉的牌所表示的数（即

a_i

和

b_j

的最小值）为

k

，那么

k

肯定是单调不递增的。这个很好理解，因为如果上一轮的输掉的牌想在下一轮获胜，当且仅当有一个比它小的牌出来了，而那张牌又会继续这么操作。所以每一轮输掉的牌的值是不递增的。

这个有什么用呢？不要急！

我们发现好像卡住了。于是仔细阅读题面，发现游戏总是恰好执行

n

轮。

为什么一定要执行

n

轮？为什么不是两者中一方打完了才算结束？这个“恰好执行

n

轮”引导着我们的思考。

提示二：如果恰好执行 $n$ 轮，那么我们是不是可以设先手出了 $i$ 张牌，然后找规律？

首先有一个显然的东西：当游戏结束时，玩家正好出完

i

张牌，那么庄家就出完了

n-i

张牌。玩家出的牌对应着

a_1

到

a_i

，庄家出的牌对应着

b_1

到

b_{n-i}

。然后玩家的下一张牌是

a_{i+1}

，庄家的下一张牌是

b_{n-i+1}

。

这样还不够直观。我们假设玩家要赢得

i

分，那么玩家要出够

i

张牌。

提示三：能不能利用上面的性质？最后输掉的牌的值有什么规律吗？

这个时候我们好像就可以利用上面发现的性质了！

我们发现每一轮输掉的牌的值是不递增的，所以最后输掉的牌肯定是

a_{1}

至

a_{i}

，

b_{1}

至

b_{n-i}

的最小值。我们发现这个最小值在这种条件下，它肯定是一直输的。那么如果玩家想得到

i

分，那么最小值一定要在庄家那边！

然后我们发现，庄家可能要出的牌是

b_1

至

b_{n-i+1}

（因为如果

n-i

张牌都打完后，玩家就要靠庄家的第

n-i+1

张牌决定自己的命运了）。我们令

a_1

至

a_i

的最小值为

x

，

b_1

至

b_{n-i+1}

的最小值为

y

。那么如果先手想要得到

i

分，当且仅当

x>y

。

提示四：随着 $i$ 的增大， $x$ 和 $y$ 有什么变化？如果有，那么就可以干什么了？

我们发现，随着

i

的增大，

x

会越来越小，而

y

会越来越大，那么玩家就可能越来越不太可能得到

i

分。

这满足单调性！

我们可以二分先手获得的分数。

但还有一个问题：先手可以交换自己的两张牌。那么如果想交换，我们肯定是要将左边的最小值替代成一个比他大的值，这样才可以使得

x

变大，才有获胜的可能。容易证明即使是这样的操作之后，我们依然满足单调性（即随着

i

的增大，玩家能获得

i

分的可能性越低）。

或许你还不会证明。没关系，我来解释一下：首先替代后的最小值肯定是原来的次小值（如果能替代的话）。那么

i

的增大，次小值会越来越小，但是

y

还是越来越大。因此玩家也就可能越来越不太可能得到

i

分。或者说替换后的数还是现在的最小值，那么同理。

最后考虑一个细节：如果不能替代，那么就不要交换。

为了方便，我们肯定是将前缀最小值和后缀最大值交换，因为这样可以成功交换的可能性最大。当然按照常规写法应该也是可以的。

代码：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000010;
const int mod=998244353;
const int INF=0x3f3f3f3f3f3f3f3f;
int n;
int a[N];
int b[N];
bool check(int r){
	int x=0,y=0;
	int mn=INF,mx=-INF;
	for(int i=1;i<=r;i++){
		if(a[i]<mn){
			mn=a[i];
			x=i;
		}
	}
	for(int i=r+1;i<=n;i++){
		if(a[i]>mx){
			mx=a[i];
			y=i;
		}
	}
    bool fl=0;
	if(x&&y&&mx>mn){//注意mx>mn的细节（还要考虑能否找到最大、最小值）
        fl=1;//满足交换条件
        swap(a[x],a[y]);
    }
	mn=INF;
	for(int i=1;i<=r;i++)mn=min(mn,a[i]);
	int mn2=INF;
	for(int i=1;i<=n-r+1;i++)mn2=min(mn2,b[i]);
	bool f=(mn>=mn2);//判断
	if(fl)swap(a[x],a[y]);//换回来
	return f;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	int l=1,r=n,mid;
	int ans=0;
	while(l<=r){//二分
		mid=(l+r)>>1;
		if(check(mid)){
			ans=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	cout<<ans<<"\n";
	return;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T=1;
	cin>>T;
	while(T--)solve();
	return 0;
}
/*
考虑能拿到i分，当且仅当min{a[1...i]}>=min{b[1...n-i+1]}
显然i变大时，左边会变小，右边会变大
那么可以二分
然后前缀最小值和后缀最大值换位置
*/

这样我们就将这道题做完了。我认为最难的就是针对“恰好打

n

轮”的思考。有时候就是题目中一个不太起眼的句子，反而是解出题目的关键。这才是我们应该去学习的。

不管怎样，加油吧……

文章操作

相关推荐

评论

CF2113D Cheater 题解