P5804 Absolute Game

Miraik · 2023-10-20 20:48:59 · 题解

结论：这个游戏等价于 Alice 先选一个数 x，Bob 再选择一个数 y。

证明：从 Bob 的角度出发。首先 Alice 可以选择任意数结束游戏，所以 Bob 显然得不到更好的结果。接下来我们构造地证明，无论 x 取何值，Bob 一定可以选到对应最优的 y。

对于 Alice 手里的每个数 a_i，我们求出满足 \lvert a_i - b_j \rvert 最小的 j，记为 c_i。

考虑每次 Alice 扔掉了一个数 a_x，由于此时 Bob 手里比 Alice 手里多一个数，此时 Bob 手里里必然存在至少一个数字满足其不为任何 Alice 手里的数的对应 c_i。那么我们将其删去后，问题变成了一个规模为 n-1 的子问题，且剩余 c 数组完全不变。于是我们证明了，无论 Alice 选择哪个数 a_x，Bob 都可以选到对应的最优值 b_{c_x}。

由此我们得到本题做法：求出 c 数组，输出其最大值即可。

时间复杂度 O(n \log n)。

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
const int inf=1000000005;
int n,a[N],b[N],ans;
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    sort(a+1,a+n+1); sort(b+1,b+n+1);
    for(int i=1;i<=n;i++){
        int j=lower_bound(b+1,b+n+1,a[i])-b;
        int c=inf;
        if(j<=n) c=min(c,b[j]-a[i]);
        if(j>1) c=min(c,a[i]-b[j-1]);
        ans=max(ans,c);
    }   cout<<ans<<'\n';
    return 0;
}