自动搬运

查看原文

来自洛谷，原作者为

	Miraik 看啊那只蝴蝶 飞过时间 落在心间

搬运于2025-08-24 22:14:30，当前版本为作者最后更新于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;
}