博弈,思维
题意:
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; }