思路
第 \(K\) 小的和显然具有单调性：给一个阈值 \(x\)，满足 \(A_i+B_j\le x\) 的对数只会随着 \(x\) 增大而增大，所以我们二分答案这个 \(x\) 即可。关键就是怎么写 check。
check
先把 \(B\) 排序。对每个 \(A_i\)，令 \(t=x-A_i\)，那么这一行能配的就是 \(B_j\le t\) 的个数，直接 upper_bound(B,t) 拿到位置就是 \(cnt_i\)。把所有 \(cnt_i\) 累加得到 \(cnt\)。如果 \(cnt\ge K\) 就说明第 \(K\) 小 \(\le x\)，check 返回 true（顺便 cnt 到 \(K\) 直接提前返回，省常数）。
auto ok = [&](ll x) -> bool {ll cnt=0;for(int i = 0;i < n; i++){ll t = x - A[i];auto it = upper_bound(B.begin(),B.end(),t);ll cnt_i=it-B.begin();cnt += cnt_i;if(cnt >= K) return true;}return false;};
实现
排序之后二分答案区间 \([A_1+B_1,;A_n+B_m]\)，用找最小 true 的写法即可。
时间复杂度：\(\Theta((n\log n+m\log m)+n\log m\log V)\)，其中 \(V\) 是和值域范围
Accepted Code (C++17)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define i128 __int128
#define ld long double
#define fir first
#define sec second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define lowbit(x) (x&-x)
using namespace std;
const int MOD=998244353;
const int MOD1=1e9+7;
//char ibuf[1<<25],*p1=buf,*p2=buf;
mt19937 mrand(random_device{}());
int rnd(int x){ return mrand() % x;}
ll qpow(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%MOD;a=a*a%MOD,b>>=1;}return res;}
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){ return a/gcd(a,b)*b;}
//C++ 17 -O2
//By MaZhaoze
int main(){ios::sync_with_stdio(0);cin.tie(0);ll n,m,K;cin >> n >> m >> K;vector<ll> A(n),B(m);for(auto &x:A) cin >> x;for(auto &x:B) cin >> x;sort(A.begin(),A.end());sort(B.begin(),B.end());auto ok = [&](ll x) -> bool {ll cnt=0;for(int i = 0;i < n; i++){ll t = x - A[i];auto it = upper_bound(B.begin(),B.end(),t);ll cnt_i=it-B.begin();cnt += cnt_i;if(cnt >= K) return true;}return false;};ll l = 0,r = 2e9;while(l <= r){ll mid = (l + r) / 2;if(ok(mid)){r = mid - 1;}else{l = mid + 1;}}cout << l;return 0;
}