题解 P5804 【[SEERC2019]Absolute Game】
FjswYuzu
·
·
题解
$\ \ \ \ \ \ \ $这道题属于动脑袋类型的题。对于这道题，我们首先求出 $c_i$ 使得 $c_i=\min\{abs(a_i-b_j)\}$。我们现在“重排”，存在 $b_i$ 使得 $abs(a_i-b_i)=c_i$，也就是最小。那么我们现在 Alice 删除了 $a_i$，我们删除与之相对应的 $b_i$。
$\ \ \ \ \ \ \ $关键来了：为什么？
$\ \ \ \ \ \ \ $我们只有两种情况：数组 a 和数组 b 取最小值是否对应。
- 当 a 数组与 b 数组取最小值是一一对应时，我们知道 $b_i$ 是使 $a_i$ 为最小的所以去掉 $a_i$ 后，bi不会使得a数组中其他数的最小值变得更小，所以 Bob 此时去掉相应的 $b_i$。Alice 丢弃一个数时一定是将使得 $c_i$ 值最小的数去掉，到最后我们就会发现我们得到的值就是 $c_i$ 数组的中的最大值。
- 当 a 数组与 b 数组取最小值不是一一对应时，Alice 还是会去掉使得 $c_i$ 值最小的那一个 $a_i$，当存在 $a_i=a_j$ 时就说明会有一个 $b_k$ 不会使得任何一个 $a_i$ 最小，此时Bob就会去掉这个数 $b_k$，到最后得到的值还是 $c_i$ 数组中的最大值。
$\ \ \ \ \ \ \ $综上所述，我们的策略是正确的。证明来自[这里](https://www.cnblogs.com/bqyb/p/11966493.html)。
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[1005],b[1005];
int Abs(int x){return x<0?-x:x;}
int main(){
int ans=-1;
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) scanf("%d",&b[i]);
for(int i=1;i<=n;++i)
{
int tmp=2147483647;
for(int j=1;j<=n;++j) tmp=min(tmp,Abs(a[i]-b[j]));
ans=max(ans,tmp);
}
printf("%d",ans);
return 0;
}
```