第十四届蓝桥杯国赛 C++ A 组 E 题——第K小的和（AC）

1. 第K小的和

前置知识点：二分，排序

1. 问题描述

给定两个序列 $A,B$，长度分别为 $n,m$。

设另有一个序列 $C$ 中包含了 $A,B$ 中的数两两相加的结果 ($C$ 中共有 $n\times m$ 个数)。问 $C$ 中第 $K$ 小的数是多少。请注意重复的数需要计算多次。例如 $1,1,2,3$ 中，最小和次小都是 $1$，而 $3$ 是第 $4$ 小。

2. 输入格式

输入的第一行包含三个整数 $n,m,K$，相邻两个整数之间使用一个空格分隔。

第二行包含 $n$ 个整数，分别表示 $A_1,A_2,\dots ,A_n$，相邻两个整数之间使用一个空格分隔。

第三行包含 $m$ 个整数，分别表示 $B_1,B_2,\dots ,B_m$，相邻两个整数之间使用一个空格分隔。

3. 输出格式

输出一行包含一个整数表示答案。

4. 样例输入

3 4 5
1 3 4
2 3 5 6

5. 样例输出

6

6. 评测用例规模与约定

• 对于 $40\%$ 的评测用例，$n,m\le 5000$，$A_i,B_i\le 1000$;
• 对于所有评测用例，$1\le n,m\le 10^5$，$1\le A_i,B_i\le 10^9$，$1\le K\le n\times m$。

7. 原题链接

第K小的和

2. 解题思路

让我们先考虑一个暴力解法：我们可以枚举出所有 $n\times m$ 个数，将其存入数组并进行排序，然后输出第 $K$ 大的数即可求解。然而，这种解法的时间复杂度为 $O(nm\log (nm))$，空间复杂度为 $O(nm)$，这将导致超时和内存溢出。

于是，我们需要寻找一个更高效的解决方案。让我们来思考一个问题：在一个序列中，第 $K$ 大的数 $x$ 有什么特性？

这需要满足数组中小于等于 $x$ 的数至少有 $K$ 个。同时，我们可以观察到，对于一个大于 $x$ 的数 $y$，序列中小于等于 $y$ 的数也一定至少有 $K$ 个。对于一个小于 $x$ 的数 $z$，序列中小于等于 $z$ 的数肯定少于 $K$ 个。

这让我们发现，寻找序列中的第 $K$ 大的数，其实等同于寻找序列中小于等于当前数的数量至少有 $K$ 个的最小值。因此，我们可以采用二分查找的策略。

当考虑答案的下界时，$A$ 和 $B$ 都取 $1$，那么 $C$ 中的数全部为 $2$，所以答案的下界是 $2$。而对于上界，当 $A$ 和 $B$ 都取 $10^9$，$C$ 中的数全部为 $2\times 10^9$，所以答案的上界是 $2\times 10^9$。

我们的关键问题在于如何编写二分查找中的 check 函数，即如何确定在 $n\times m$ 个数中，有多少个数比一个给定的整数 $x$ 小。直接遍历这 $n\times m$ 个数显然是不可行的，我们需要找到一个优化的方法。一个可行的策略是先将 $B$ 数组排序，然后遍历数组 $A$。对于每个 $A_i$，我们需要在 $B$ 数组中找到满足 $B_j+A_i\le x$ 的最大下标 $j(j\in [1,m])$。

这个问题等价于在 $B$ 数组中找到最大的数，使其小于等于 $x-A_i$，这显然是一个基础的二分查找问题。这样我们就能以 $O(\log m)$ 的复杂度统计每个 $A_i$ 的贡献，加上遍历数组 $A$ 的复杂度为 $O(n)$，因此每次 check 函数的复杂度为 $O(n\log m)$。

对于每次二分查找的数 $x$，在 check 函数中，如果我们统计到有至少 $K$ 个数小于等于 $x$，我们就返回 true，否则返回 false。

因此，这种解法的时间复杂度为：$O(n\log (m)\log (2\times 10^9))$。

3. AC_Code

• C++

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL n, m, k;
void solve() {
   
    cin >> n >> m >> k;

    vector<int> a(n), b(m);
    for (int i = 0; i < n; ++i) {
   
        cin >> a[i];
    }

    for (int i = 0; i < m; ++i) {
   
        cin >> b[i];
    }

    sort(b.begin(), b.end());

    LL l = 2, r = 2e9;
    auto check = [&](LL x) {
   
        LL res = 0;
        for (int i = 0; i < n; ++i) {
   
            res += upper_bound(b.begin(), b.end(), x - a[i]) - b.begin();
        }
        return res >= k;
    };
    while (l < r) {
   
        LL mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << r << '\n';
}
int main() {
   
    ios_base ::sync_with_stdio(false);
    cin.tie(0);
    cout << setiosflags(ios::fixed) << setprecision(2);
    int t = 1;
    while (t--) {
   
        solve();
    }
    return 0;
}

• Java

import java.util.*;
import java.io.*;

public class Main {
   
    static long n, m, k;
    static long ans = 0;
    
    static boolean check(long x, long[] a, long[] b) {
   
        long res = 0;
        for (int i = 0; i < n; ++i) {
   
            res += upperBound(b, x - a[i]);
        }
        return res >= k;
    }

    static int upperBound(long[] a, long x) {
   
        int l = 0, r = a.length;
        while (l < r) {
   
            int mid = (l + r) / 2;
            if (a[mid] <= x) l = mid + 1;
            else r = mid;
        }
        return l;
    }

    public static void main(String[] args) {
   
        Scanner sc = new Scanner(System.in);
        n = sc.nextLong();
        m = sc.nextLong();
        k = sc.nextLong();
        long[] a = new long[(int) n];
        long[] b = new long[(int) m];
        for (int i = 0; i < n; ++i) {
   
            a[i] = sc.nextLong();
        }
        for (int i = 0; i < m; ++i) {
   
            b[i] = sc.nextLong();
        }
        Arrays.sort(b);
        long l = 2, r = (long) 2e9;
        while (l < r) {
   
            long mid = l + (r - l) / 2;
            if (check(mid, a, b))
                r = mid;
            else
                l = mid + 1;
        }
        System.out.println(r);
    }

}

• Python

import bisect

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(list(map(int, input().split())))

l, r = 2, int(2e9)

def check(x):
    res = 0
    for i in range(n):
        res += bisect.bisect_right(b, x - a[i])
    return res >= k

while l < r:
    mid = l + (r - l) // 2
    if check(mid):
        r = mid
    else:
        l = mid + 1

print(r)