CSP-S 提高级 · CSP 2024 提高级第一轮 第 19 题

三、完善程序（单选题，每小题 3 分，共计 30 分）

第 1 题

（序列合并） 有两个长度为 $N$ 的单调不降序列 $A$ 和 $B$，序列的每个元素都是小于 $10^9$ 的非负整数。在 $A$ 和 $B$ 中各取一个数相加可以得到 $N^2$ 个和，求其中第 $K$ 小的和。上述参数满足 $N \leq 10^5$ 和 $1 \leq K \leq N^2$。

#include <iostream>
using namespace std;

const int maxn = 100005;

int n;
long long k;
int a[maxn], b[maxn];

int* upper_bound(int *a, int *an, int ai) {
    int l = 0, r = ___①___;
    while (l < r) {
        int mid = (l+r)>>1;
        if (___②___) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return ___③___;
}

long long get_rank(int sum) {
    long long rank = 0;
    for (int i = 0; i < n; ++i) {
        rank += upper_bound(b, b+n, sum - a[i]) - b;
    }
    return rank;
}

int solve() {
    int l = 0, r = ___④___;
    while (l < r) {
        int mid = ((long long)l+r)>>1;
        if (___⑤___) {
            l = mid + 1;
        } else {
  

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考的是经典的双有序数组合并求第 K 小和。拿到题先想：两个数组各取一个数，和的范围很明确，直接暴力枚举是 O(N^2) 肯定超时。所以核心思路是二分答案——猜一个和 mid，然后快速算出有多少对数的和小于等于 mid，如果数量不足 K 就调大 mid，否则调小。至于怎么快速算数量？利用数组有序的特性，对每个 a[i]，用二分查找（upper_bound）在 b 里找第一个比 (mid - a[i]) 大的位置，这个位置下标就是满足条件的 b 的元素个数。把五个空填对，逻辑就通了。

最容易栽跟头的地方往往不在算法框架，而在细节上。第一，upper_bound 函数的右边界 r 填错，很多人直觉填 an-a-1，结果区间变成 [0, an-a-1)，少查了一个元素，导致计数偏小，答案偏大。第二，二分查找的比较条件搞反，upper_bound 是找“第一个大于”的元素，所以条件必须是 a[mid] > ai，填成大于等于就会把本该包含的数排除在外，或者反之。第三，返回指针时写成了 a+l+1 或 a+l-1，这直接导致返回的指针偏移，计数完全乱套。第四，二分答案的右边界，有人会写成 a[n]+b[n]，数组下标越界了，或者写成 2*maxn，虽然数值大但不够精确，没必要。第五，二分判断条件，get_rank(mid) < k 时说明 mid 太小，要往右找，填成 <= 或 > 都会让循环死锁或收敛到错误值。这些坑都是命题人最爱挖的，一定要在动手前把 upper_bound 的语义和二分答案的单调性彻底想清楚。

考察知识点

分治算法 / 二分答案 / 双指针 / upper_bound 二分查找

概念定义

• 第 K 小问题：在两个有序数组中各取一数求和，求第 K 小的和。直接枚举所有 N^2 种组合显然超时，必须借助有序性加速。
• 二分答案：在答案的单调范围内进行二分搜索，每次验证当前答案是否可行。这里验证的方法是：统计有多少对 (a[i], b[j]) 的和 <= mid，若数量 < K，说明 mid 太小，答案在右半区；反之在左半区。
• upper_bound：在有序数组中查找第一个大于给定值的元素的位置。C++ STL 中对应函数，这里我们手写版本：输入数组 a，目标值 ai，返回指向第一个 > ai 的元素的指针。若没有大于 ai 的元素，则返回 a + an（即数组末尾之后）。注意返回的是指针，减去数组首地址 a 得到的就是下标。

逐步推导

整体算法

求第 K 小的和 = 二分答案 sum，统计有多少对 (a[i], b[j]) 的和 <= sum。如果计数 < K，说明答案太小；否则缩小上界。

逐空分析

① upper_bound 右边界： upper_bound 要在区间 [l, r) 内查找，初始 l=0，r 应该是数组元素个数，即 an - a。填 an-a。

② upper_bound 判断条件： upper_bound 找第一个 > ai 的元素，所以条件是 a[mid] > ai。

③ 返回指针： 循环结束后 l 指向第一个 > ai 的元素下标，返回指针 a+l。

④ 二分答案右边界： 和的范围 [0, a[n-1]+b[n-1]]。填 a[n-1]+b[n-1]。

⑤ 二分条件： get_rank(mid) < k 时 l=mid+1，否则 r=mid。

避坑指南

二分答案的边界条件和比较符号容易搞反。记住：找第 K 小 = 计数和 <= mid 的对数，若少于 K 个则增大 mid。upper_bound 的右边界和返回指针也极易出错，务必确认区间是半开半闭 [l, r)，且返回的是第一个满足条件的元素位置。

技巧总结

“第 K 小”问题的通用解法框架：二分答案 + 计数验证。外层二分 O(log V)，内层 O(n) 或 O(n log n) 计数。