标签：博弈论，二分
题目
给定 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;
}
