Codeforces Round #330 (Div. 1)

A.Warrior and Archer

$\mathtt{Difficulty}$=$\mathtt{2300}$
这道题目其实算是一道结论题
我们首先将序列排个序
因为 A 要使两点距离尽可能近
然而 B 要使两点距离尽可能远
我们首先想到：

• A 肯定从两边开始取
• B 肯定从中间开始取

这样破坏道只剩 $2$ 个点的时候
因为一共少了 $n-2$ 个点
所以每人取了 $\frac{n}{2}-1$ 个点
然后我们就得到了这道题的核心结论,即：

枚举距离为 $\frac{n}{2}$ 的点，再取最小值即可

代码不难写出

#include<bits/stdc++.h>
#define BetterIO ios::sync_with_stdio(false)
using namespace std;
int N,A[200001];
int main(void)
{
	BetterIO;
	#ifndef ONLINE_JUDGE
	freopen("IN.in","r",stdin);
	#endif
	register int i,j;cin>>N;
	for(i=1;i<=N;i++)cin>>A[i];
	sort(A+1,A+N+1);
	register int Ans(INT_MAX);
	for(i=1;(j=i+N/2)<=N;i++)Ans=min(Ans,A[j]-A[i]);
	cout<<Ans<<endl;
	return 0;
}