[ABC302D] Impartial Gift
题目要求：给定长度分别为 $n,m$ 两个数组 $a,b$，求 $\underset{i\in[1,n],j\in[1,m],|a_i-b_j|\leq d}{\max}a_i+b_j$
对于每个 $a_i$，我们可以在排好序的 $b$ 中二分查找处于 $[a_i-d,a_i+d]$ 的数所对应的 $b$ 的区间 $[l,r]$，此处可以使用 std::lower_bound 和 std::upper_bound。
根据函数的定义，当区间内没有满足条件的值的时候，$l>r$，我们特判这种情况。我们知道 $a + b > a + c(b>c)$，所以 $\underset{j\in[l,r]}{\max}a_i+b_j=a_i+b_r$。
所以我们最后只需要求出 $a_i+b_r$ 的最大值或判断无解即可。
#include<iostream>
#include<algorithm>
const int sz = 2e5 + 10;
using ll = long long;
ll arr[sz], barr[sz];
int main() {
int n, m;
long long d;
std::cin >> n >> m >> d;
for (int i = 1; i <= n; i++) std::cin >> arr[i];
for (int i = 1; i <= m; i++) std::cin >> barr[i];
std::sort(barr + 1, barr + m + 1);
ll ans = 0;
for (int i = 1; i <= n; i++) {
int l = std::lower_bound(barr + 1, barr + m + 1, arr[i] - d) - barr;
int r = std::upper_bound(barr + 1, barr + m + 1, arr[i] + d) - barr - 1;
if (l > r) continue;
ans = std::max(ans, arr[i] + barr[r]);
}
std::cout << (ans == 0 ? -1 : ans) << "\n";
return 0;
}