CSP-S 2022 第一轮 第34题：完善程序（第 19 题）第 1 空

题目

三 完善程序（单选题，每小题 3 分，共计 30 分）
(1)（归并第 k 小） 已知两个长度均为 n 的有序数组 a1 和 a2（均为递增序，但不保证严 格单调递增），并且给定正整数 k（1≤k≤2n），求数组 a1 和 a2 归并排序后的数组里 第 k 小的数值。

试补全程序。

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

int solve(int *a1, int *a2, int n, int k) {
    int left1 = 0, right1 = n - 1;
    int left2 = 0, right2 = n - 1;
    while (left1 <= right1 && left2 <= right2) {
        int m1 = (left1 + right1) >> 1;
        int m2 = (left2 + right2) >> 1;
        int cnt = ①;
        if (②) {
            if (cnt < k) left1 = m1 + 1;
            else right2 = m2 - 1;
        } else {
            if (cnt < k) left2 = m2 + 1;
            else right1 = m1 - 1;
        }
    }
    if (③) {
        if (left1 == 0) {
            return a2[k - 1];
        } else {
            int x = a1[left1 - 1], ④;
            return std::max(x, y);
        }
    } else {
            if (left2 == 0) {
                return a1[k - 1];
            } else {
                int x = a2[left2 - 1], ⑤;
                return std:: max(x, y);
            }
    }
}

①处应填（ ）

选项

• A. (m1 + m2) * 2
• B. (m1 - 1) + (m2 - 1)
• C. m1 + m2
• D. (m1 + 1) + (m2 + 1)

答案

C

题解

选 C：m1 + m2。这道题不能只数中点之前共有多少元素，还要看后续分支和最后的返回语句怎样配合。

以②比较 a1[m1] < a2[m2] 为例：当 m1 + m2 < k，程序令 left1 = m1 + 1，可能刚好跨过第 k 小的候选；结尾会再用 a1[left1-1] 参与取最大值，把它保留下来。否则缩小另一数组的右边界。另一分支对称，所以①应使用两个中点下标之和，而不是选项 D 的两个前缀元素数之和。

可以用最小反例排除 D：a1=[1]、a2=[2]、k=2 时，两边中点都是 0，填 D 得 cnt=2，程序会把 right2 改成 -1；后续无论③怎么填，都会访问越界位置，不能正确返回 2。①填 C 才与后续逻辑相配。其余空白尚未给出，不能仅凭这一空保证整段程序没有别的边界问题。