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

本文主要是介绍第十四届蓝桥杯国赛 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;elsel = 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;elsel = mid + 1;}System.out.println(r);}}

• Python

import bisectn, 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 = 0for i in range(n):res += bisect.bisect_right(b, x - a[i])return res >= kwhile l < r:mid = l + (r - l) // 2if check(mid):r = midelse:l = mid + 1print(r)

这篇关于第十四届蓝桥杯国赛 C++ A 组 E 题——第K小的和（AC）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---