CF594A 题解

题面

来个不一样的证明。

根据样例，我们可以有一个直觉：两点之间一定距离 \(\frac n2\)，答案为这样的点对之间 \(\Delta x\) 的最小值。

直接交上去，发现这是对的。为什么呢？

先证明上界：先手可以让答案小于等于 两点距离 \(\frac n2\) 点对的 \(\Delta x\) 的最小值。

这是容易的：先手只要找到这对点，把点对两侧全部拿走就行了。数量为 \(\frac n2-1\)。

再证明下界：后手可以让答案大于等于 两点距离 \(\frac n2\) 点对的 \(\Delta x\) 的最小值。

考虑如果先手取点 \(i\)，后手就取距离这个点 \(\frac n2\) 的点，显然这是唯一的。

注意到这样相当于每回合取走一对距离为 \(\frac n2\) 的点对。\(\frac n2-1\) 回合后就剩下一对距离为 \(\frac n2\) 的点对了。

答案显然大于等于 两点距离 \(\frac n2\) 点对的 \(\Delta x\) 的最小值。

所以答案就是一开始所猜的。

所以猜结论很重要。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2e5 + 5;
int a[N], n;

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    sort(a + 1, a + n + 1);
    int ans = 1e9;
    for(int i = n / 2 + 1; i <= n; i ++)
        ans = min(ans, a[i] - a[i - n / 2]);
    cout << ans;

    return 0;
}