割と良問の気配だっただけにもったいない。
http://codeforces.com/contest/594/problem/A
問題
N個(偶数)の整数A[i]が与えられる。
２人プレイヤーは、これらの要素を交互に１個ずつ消していく。
最終的に数値が残り２個になるまで要素を消して行き、最終スコアは残った２要素の値の差の絶対値となる。
先手はスコアを最小化、後手は最大化したい場合、最終的なスコアはどうなるか答えよ。
解法
双方(N-2)/2個の要素を消すことができる。
後手は連続した(N-2)/2個の要素を消すことで、先手が残りをどう消してもその(N-2)/2個の要素の両隣に残る要素の差以上のスコアを得られる。
よって、Aをソートし、A[i+(N-2)/2+2]-A[i]が最大となるiを総当たりすると良い。
int N; ll X[202020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>X[i]; sort(X,X+N); int del=N-2; int A=(del+1)/2,B=del/2; ll ma=1LL<<61; FOR(i,N) if(i+B+1<N) ma=min(ma,X[i+B+1]-X[i]); cout<<ma<<endl; }
まとめ
Nが奇数だと、最後に先手が処理できるので問題がややこしくなる、ってことでいいのかな？
