题解：CF1949B Charming Meals
ST_AS_IS_ZHY
·
·
题解
题目传送门
update:2024.5.21 删除反抄袭
题意
给与两个数组 a 和 b，将其中的数两两匹配，要求匹配后每组数字的差值中最小值最大，求这个值。
思路
首先将 a 和 b 升序排序，此时取任意 p 满足 1 \le p \le n，可证对于 1 \le i \le p，最佳匹配为 a_i 与 b_{p + i} 匹配， b_i 与 a_{p + i} 匹配。
证明部分
若存在 i + p \le j \le n
使得 a_i 与 b_j 匹配优于 a_i 与 b_{p + i} 匹配，则改变匹配使得a_i 与 b_j 匹配， $a_{j - p}
#### 证毕
所以只需要枚举每一个 $p$ ，取答案最大值即可。复杂度为
${O} (n^ 2)$.
## 代码部分
```cpp
// Problem: Charming Meals
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1949B
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 5e3 + 10;
int n, a[N], b[N], vis[M], ans;
// bool check(int mid)
// {
// memset(vis, 0, sizeof vis);
// if(max(abs(a[1] - b[n]), abs(a[n] - b[1])) < mid) return false;
// cout << "mid = " << mid << '\n';
// for(int i = 1; i <= n; i ++)
// {
// int cnt = upper_bound(b + 1, b + n + 1, a[i]) - b, f1 = 0, f2 = 0;
// for(int j = cnt; j <= n; j ++) if(b[j] - a[i] >= mid && !vis[j]) {vis[j] = true, f1 = j; break;}
// for(int j = cnt - 1; j >= 1; j --) if(a[i] - b[j] >= mid && !vis[j]) {vis[j] = true, f2 = j; break;}
// cout << "f1 = " << b[f1] << " f2 = " << b[f2] << '\n';
// if(!f1 && !f2) return false;
// else if((f1 && !f2) || (!f1 && f2)) continue;
// else
// {
// if(b[f1] - a[i] > a[i] - b[f2]) vis[f1] = false;
// else vis[f2] = false;
// }
// }
// return true;
// }
int work(int t)
{
int minn = 2e9 + 10;
for(int i = 1; i <= t; i ++) minn = min(minn, abs(a[i] - b[n - t + i]));
for(int i = t + 1; i <= n; i ++) minn = min(minn, abs(b[i - t] - a[i]));
return minn;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T; cin >> T;
while(T --)
{
cin >> n; ans = -1;
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 ++) ans = max(ans, work(i));
cout << ans << '\n';
}
return 0;
}
```