Game【省选模拟赛】

讨论的智慧


本文总阅读量
Posted by yjjr's blog on March 27, 2018

标签:博弈论,二分

题目

给定 n 个数字,两个人轮流删去一个,到剩余两个数字结束,第一个人最大化差,第二个人最小化,问最后的差是多少。

分析

先考虑两种特殊情况(subtask)

  • 当n为奇数,最大化的那个人先手行动时,答案出现的形式肯定是最大化的从中间拿掉一个,最小化的从两边拿掉
  • 答案就是最小的一对\(abs(a[i]-a[i+\lceil \frac n 2\rceil])\)
  • 证明这个答案是正确的,显然这个状态对于最大化的是可达的,对于最小化的来说,考虑一共有\(\lfloor \frac n 2 \rfloor -1\)次操作机会,只需要选定这一对,然后把外面的全删掉就可行了

  • 当n为奇数,最小化的那个人先手行动
  • 考虑二分的做法,对于最小化的人来说,每次二分来检验是否可以将答案限制在二分值之下
  • 至于判断和检验的话,直接贪心将石子划分成最少的堆就好了,如果堆的数量不超过\(\lceil \frac n 2 \rceil\)就符合条件了
  • 证明可以用数学归纳法,我们考虑证明最终只会剩下一堆,可以通过归纳证明,当还剩 \(i\)步的时候,石子不会超过\(i+1\)堆。发现石子个数恰好是\(2i+1\)个,如果现在恰好堆是满的,那么一定有一堆只有一个,删去即可,完成归纳;不可达的证明,我们可以考虑贪心的时候,从前往后分,那么任意两个堆头一定距离超过二分值,那么就不可能把堆删光,于是得证。

另外的两种情况,直接判断下就可以了,和前两种特殊情况对应的

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline ll read(){
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
#define inf 1e9
const int maxn=2e5+6;
int n,a[maxn],f[maxn];
char s[maxn];
inline bool check(int x){
	int last=1;
	rep(i,1,n){
		while(a[i]-a[last]>x)last++;
		f[i]=f[last-1]+1;
	}
	return f[n]<=(n+1)/2;
}
int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout); 
	while(scanf("%d%s",&n,s)!=EOF){
		rep(i,1,n)a[i]=read();
		int last=(n&1)^(s[0]=='s');
		if(!last){
			int ans=inf;
			rep(i,1,n-(n+1)/2)ans=min(ans,a[i+(n+1)/2]-a[i]);
			cout<<ans<<endl; 
		}else{
			int l=0,r=inf;
			while(l<r){
				int mid=(l+r)>>1;
				if(check(mid))r=mid;else l=mid+1;
			}
			cout<<l<<endl;
		}
	}
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr