P1631 序列合并

把二维和表看成若干条有序序列

问题

P1631 序列合并
有两个长度均为 $n$ 的单调不降序列 $A,B$。从两个序列中各选一个数相加，一共能得到 $n^2$ 个和，需要按从小到大的顺序输出其中最小的 $n$ 个。不能显式生成所有和，否则时间与空间都会达到 $O(n^2)$。

数据规模：$1\le n\le10^5$，$1\le A_i,B_i\le10^9$。

我最开始觉得它像双指针，因为每次输出一个和以后，确实只有某个下标需要向后移动。不过普通双指针只比较两个候选，这里同时有 $n$ 行候选，可以扩展到 $n$ 指针。

固定 $i$ 后，$A_i+B_1,A_i+B_2,\dots,A_i+B_n$ 本身是一条有序序列。

所以原问题可以转化为，我在这 $n$ 条序列中，挑选出 $n$ 个最小的数，也就是所谓的 “多路合并”。

先把每一条序列的首项 $(A_i+B_1,i,1)$ 放入小根堆。每次弹出当前最小值后，若它来自第 $i$ 条序列的第 $j$ 项，就把同一条序列的下一项 $(A_i+B_{j+1},i,j+1)$ 加入堆中；弹出 $n$ 次便得到答案。

堆中始终只保留每条序列尚未输出部分的最小元素，因此堆顶就是所有未输出元素中的最小值。时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

▶

P1631

ll a[maxn], b[maxn];

struct Node {
    ll val;
    int i, j;
    bool operator < ( const Node &oth ) const {
        return val > oth.val;
    }
};

void solve( ) {
    int n = read( );
    for( int i = 1; i <= n; i ++ ) a[i] = read( );
    for( int i = 1; i <= n; i ++ ) b[i] = read( );

    priority_queue<Node> pq;
    for( int i = 1; i <= n; ++ i ) {
        pq.push({ a[i] + b[1], i, 1 });
    }

    for( int k = 1; k <= n; ++ k ) {
        auto [val, i, j] = pq.top( );
        pq.pop( );
        cout << val << " ";
        if( j < n ) {
            pq.push({ a[i] + b[j + 1], i, j + 1 });
        }
    }
}