博弈,思维

题意:

https://codeforces.com/gym/102392/problem/I
##分析
先直接给出方案:
考虑到我们最后将留下a[i]
我们求出对于每个a[i]找差值最小的b[j],即我们选a[i]时最终将会留下b[i]
最后再遍历找出差值最大的a[i]

为什么会这样呢?

我们可以想象,倘若我留下了a[i]那么对方将会留下b[j]以保证差距最小
对方都已经知道了,所有a[i]对应的最小差值的b[j]
那么在每一次博弈中
Alice 拿去a[i]
那么 Bob 拿去b[j] (与a[i]对应的最优b[j])
那么最终无论你Alice取到那个a[i]我Bob都可以选出那个最优的b[j]
既然如此,Alice自然要选出最后对其来说最优的那个a[i]了
考虑到数据范围只有1000我们直接暴力就好

代码如下,注意细节

#include<iostream>
#include<algorithm>
using namespace std;
int n, a[1100], b[1100];

int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 0;i < n;i++)cin >> a[i];
    for (int i = 0;i < n;i++)cin >> b[i];
    int ans = 0;
    for (int i = 0;i < n;i++) {
        int res = 1e9;
        for (int j = 0;j < n;j++) {
            res = min(res, abs(b[j] - a[i]));
        }ans = max(ans, res);
    }cout << ans << endl;
}