序列合并

题意

两个长度为 $n$ 的单调不降序列 $A$ 和 $B$ ，产生 $n^2$ 个两两和 $A_i+B_j$ ，输出其中最小的 $n$ 个。

思路

直接枚举所有 $n^2$ 个和再排序，时间 $O(n^2 \log n)$ ，对 $n=10^5$ 不可行：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-05 09:50
 * update_at: 2026-08-05 09:50
 */
// brute.cpp：小数据暴力解，直接生成所有 N² 个和并排序取前 N 个。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    // 生成所有 N² 个和
    vector<long long> sums;
    sums.reserve(n * n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            sums.push_back(a[i] + b[j]);

    sort(sums.begin(), sums.end());

    // 输出前 N 个最小的和
    for (int i = 0; i < n; i++) {
        if (i) cout << " ";
        cout << sums[i];
    }
    cout << "\n";

    return 0;
}

暴力把所有两两和全部生成后排序。关键瓶颈是 $n^2$ 太大。

关键观察：固定 $A[i]$ 后， $A[i]+B[0] \leqslant A[i]+B[1] \leqslant \cdots \leqslant A[i]+B[n-1]$ 。可以把 $n$ 行各看成一条有序流，用最小堆同时维护 $n$ 条流的头部。

以官方样例 $A=[2,6,6]$ , $B=[1,4,8]$ 为例，堆的操作过程如下：

步骤	堆状态（弹出前）	弹出	补入
1	{(3,0,0), (7,1,0), (7,2,0)}	3	(6,0,1)
2	{(6,0,1), (7,1,0), (7,2,0)}	6	(10,0,2)
3	{(7,1,0), (7,2,0), (10,0,2)}	7	(10,1,1)

弹出 3, 6, 7 即为答案。每次弹出后只补入同一条流的下一个元素，保证不遗漏也不重复。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-05 09:50
 * update_at: 2026-08-05 10:30
 */
// 多路归并：固定 A[i] 后 A[i]+B[j] 单调不降，用堆合并 N 条有序流，弹 N 次即得最小 N 个和。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
long long a[MAXN], b[MAXN]; // 两个单调不降序列

// 堆元素：(和, 行号, 列号)
struct HeapNode {
    long long sum;  // 和
    int row;        // 行号
    int col;        // 列号
    bool operator<(const HeapNode& o) const { return sum > o.sum; } // 小根堆
};
priority_queue<HeapNode> pq;

long long ans[MAXN]; // 答案数组

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    // 初始把每行的第一个元素 A[i]+B[0] 入堆
    for (int i = 0; i < n; i++)
        pq.push({a[i] + b[0], i, 0});

    for (int k = 0; k < n; k++) {
        HeapNode node = pq.top();
        pq.pop();
        ans[k] = node.sum;
        // 同一行的下一个元素入堆
        if (node.col + 1 < n)
            pq.push({a[node.row] + b[node.col + 1], node.row, node.col + 1});
    }

    for (int i = 0; i < n; i++) {
        if (i) cout << " ";
        cout << ans[i];
    }
    cout << "\n";

    return 0;
}

复杂度

时间 $O(n \log n)$ ，空间 $O(n)$ 。

总结

不要枚举 $n^2$ 个和；利用每行有序的性质，用堆做多路归并，每次弹出全局最小并补入同一条流的下一个元素。

图示解析

text

1
2
3
4
5
6
7矩阵 A[i]+B[j]       堆多路归并路线
  B[0] B[1] B[2]
A[0]  3    6   10    行0: 3 → 6 → 10
A[1]  7   10   14    行1: 7 → 10 → 14
A[2]  7   10   14    行2: 7 → 10 → 14

弹出顺序: 3(行0) → 6(行0) → 7(行1) → ...

每行是有序流，堆维护每行当前最小值。弹出某行后，该行的下一个元素入堆。这样只访问前 $n$ 个最小元素，跳过了其余 $n^2-n$ 个较大的和。

目录

题意

思路

代码

复杂度

总结

图示解析