算法

(二分答案) $O(n\log^2)$

假设答案为 $x$，原问题可以转化成满足小于 $x$ 的数对和不超过 $k-1$ 个中 $x$ 的最大值

二分答案即可

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    int n, m; ll k;
    cin >> n >> m >> k;

    vector<int> a(n), b(m);
    rep(i, n) cin >> a[i];
    rep(i, m) cin >> b[i];

    ranges::sort(a);
    ranges::sort(b);

    ll ac = 0, wa = 2e9+5;
    while (abs(ac-wa) > 1) {
        ll wj = (ac+wa)/2;

        auto ok = [&]{
            ll cnt = 0;
            rep(i, n) {
                int j = lower_bound(b.begin(), b.end(), wj-a[i]) - b.begin();
                cnt += j;
            }
            return cnt <= k-1;
        }();

        (ok ? ac : wa) = wj;
    }

    cout << ac << '\n';

    return 0;
}

其实也可以把判定条件里的二分去掉换成双指针，这样复杂度就少了一个 $\log$

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    int n, m; ll k;
    cin >> n >> m >> k;

    vector<int> a(n), b(m);
    rep(i, n) cin >> a[i];
    rep(i, m) cin >> b[i];

    ranges::sort(a);
    ranges::sort(b, greater<>());

    ll ac = 0, wa = 2e9+5;
    while (abs(ac-wa) > 1) {
        ll wj = (ac+wa)/2;

        auto ok = [&]{
            ll cnt = 0; int bi = 0;
            rep(ai, n) {
                while (bi < m and a[ai]+b[bi] >= wj) ++bi;
                cnt += m-bi;
            }
            return cnt <= k-1;
        }();

        (ok ? ac : wa) = wj;
    }

    cout << ac << '\n';

    return 0;
}