原题大意
定义一个函数maxMatching(A,B,y)，其输入包含两个整数数组 A 和 B 以及一个整数 y，返回一个整数。
记数组 A 的大小为 N，数组 B 的大小为 M。考虑一个由 {a1, a2, … , aN } 和 {b1, b2, … , bM}
两个顶点集构成的二分图。节点 ai 和 bj 之间存在边相连当且仅当 abs(Ai - Bj ) <= y。函数maxMatching(A,B,y)便返回这个这个二分图的最大匹配。
现在给你两个整数数组 C 和 D 和一个整数 e，请你输出下面这段程序的运行结果：
ans = maxMatching(C, D, e)
FOR x = -2e9..2e9
FOR i = 1..N
F[i] = C[i] + x
ans = max(ans, maxMatching(F, D, e))
output ans
算法分析
先看看哪些X是有用的，即有用的事件点有哪些。对于c[i], d[j]，可以用的事件点只有两个，通过计算可得。然后把事件点排序，发现每个c能匹配的d是一段不断往下移的区间。因此可以迅速求出最大匹配。
最后枚举时代码那样写的原因：
程序代码
#include <bits/stdc++.h>
using namespace std;
const int N = 500 + 5;
int T, n, m, e;
int a[N], b[N];
vector<int> v;
int main(){
freopen("input.txt", "r", stdin);
cin >> T;
while(T--){
cin >> n >> m >> e;
for(int i = 1;i <= n; i++)
cin >> a[i];
for(int i = 1; i <= m; i++)
cin >> b[i];
sort(a+1,a+1+n);
sort(b+1,b+1+m);
v.clear();
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
v.push_back(b[j] + e - a[i]);//临界x即为触发点
v.push_back(b[j] - e - a[i]);
}
}
sort(v.begin(), v.end());
//v里面放可用的x，并排序然后贪心
int bestAns = 0;
for(int i = 0; i < v.size(); i++){
if(i==0||v[i] != v[i-1])
{
int ans = 0;
int now = 1;
//此处匹配参见上图
for(int j = 1; j <= n; j++){
while(now <= m && b[now] < a[j] + v[i] - e){
now++;
}
if(now > m || b[now] > a[j] + v[i] + e){
continue;
}
ans++;
now++;
}
bestAns = max(ans, bestAns);
}
}
cout << bestAns << endl;
}
return 0;
}