题目网址：
https://www.luogu.com.cn/problem/P10417

题目描述

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

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

输入格式

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

第二行包含 n 个整数，分别表示 A1,A2,…,An，相邻两个整数之间使用一个空格分隔。

第三行包含 m 个整数，分别表示 B1,B2,…,Bm，相邻两个整数之间使用一个空格分隔。

输出格式

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

输入输出样例

输入 #1

3 4 5
1 3 4
2 3 5 6

输出 #1

6

说明/提示

【评测用例规模与约定】

• 对于 40% 的评测用例，n,m≤5000，Ai,Bi≤1000;
• 对于所有评测用例，1≤n,m≤105，1≤Ai,Bi≤109，1≤K≤n×m。

题解：

算法思路：双指针与二分搜索

核心思想

问题转化：

• 第 K小的数 x满足：C中小于等于 x的数的个数 ≥K
• 最小满足条件的 x即为答案

二分框架：

• 搜索范围：[Amin+Bmin,Amax+Bmax]
• 判断条件：统计 C中小于等于 mid的数的个数 cnt

高效统计：

• 先对 A和 B排序
• 使用双指针在 O(n+m)时间内计算 cnt

双指针优化原理

• 单调性利用：A递增，B递增
• 指针移动：j从 m开始递减，对每个 Ai移动 j使 Bj≤x-Ai
• 累加计数：cnt=∑i=1nj

代码详细注释

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

const int MAXN = 1e5 + 5;
ll n, m, k, ans;
ll a[MAXN], b[MAXN];  // 存储序列A和B

// 检查函数：统计C中小于等于x的数的个数是否<k
bool check(ll x) {
    ll cnt = 0;        // 统计小于等于x的数的个数
    int j = m;         // B的指针，从最大值开始

    // 遍历A（A已升序排序）
    for (int i = 1; i <= n; i++) {
        // 优化：若A_i已大于x，后续A_i更大，直接退出
        if (a[i] > x) break;
        
        // 移动j指针：找到满足B_j <= x - A_i的最大j
        while (j >= 1 && b[j] > x - a[i]) {
            j--;
        }
        // 累加当前A_i对应的数量（j即满足条件的B的元素个数）
        cnt += j;
    }
    // 返回是否小于k
    return cnt < k;
}

// 二分搜索函数：寻找最小的x使得C中小于等于x的数的个数>=k
ll search(ll l, ll r) {
    while (l <= r) {
        ll mid = (l + r) >> 1;  // 取中点
        if (check(mid)) {
            // 小于等于mid的个数不足k，需增大mid
            l = mid + 1;
        } else {
            // 个数已足够，尝试缩小mid
            r = mid - 1;
        }
    }
    return l;  // l是最小满足条件的x
}

int main() {
    // 输入处理
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];
    
    // 排序A和B（升序）
    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);
    
    // 确定二分边界：最小和与最大和
    ll low = a[1] + b[1];
    ll high = a[n] + b[m];
    
    // 二分搜索第K小的数
    ans = search(low, high);
    cout << ans << endl;
    
    return 0;
}

关键步骤图解

1. 双指针工作流程

A = [1,2] (n=2)
  B = [3,4] (m=2)
  x = 5
  
  遍历A：
    i=1 (A_i=1): 
        x - A_i = 4
        j=2 (B_j=4) -> 4<=4 → j=2 → cnt+=2
    i=2 (A_i=2):
        x - A_i = 3
        j=2 (B_j=4>3) → j-- → j=1 (B_j=3<=3) → cnt+=1
  总cnt=3 → 满足>=k=3

2. 二分搜索过程

3. 复杂度优化对比

复杂度分析

• 时间复杂度：O((n+m)logΔ)
• Δ=max_sum-min_sum≤2×109，logΔ≈31
• 空间复杂度：O(n+m)
• 存储序列 A和 B