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

2024 年 8 月 3 日 16点热度 0人点赞 0条评论

1. 第K小的和

前置知识点：二分，排序

1. 问题描述

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

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

2. 输入格式

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

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

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

3. 输出格式

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

4. 样例输入

3 4 5
1 3 4
2 3 5 6

5. 样例输出

6. 评测用例规模与约定

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

7. 原题链接

第K小的和

2. 解题思路

让我们先考虑一个暴力解法：我们可以枚举出所有 $\times m$ 个数，将其存入数组并进行排序，然后输出第 $K$ 大的数即可求解。然而，这种解法的时间复杂度为 $\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$ 中的数全部为 $\times 10^9$ ，所以答案的上界是 $\times 10^9$ 。

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

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

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

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

3. AC_Code

#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)