题解 序列合并

题目链接

首先不难想到，最小数的一定是 \(a_1+b_1\)，次小的数是 \(a_1+b_2\) 和 \(a_2+b_1\) 中小的。

得出结论，若 \(a_i+b_j\) 是第 \(k\) 小，那么 \(a_{i+1}+b_j\) 和 \(a_i+b_{j+1}\) 有可能成为第 \(k+1\) 小。

这是一个很优秀的性质，这意味着我们可以通过最小值推出次小值，再通过次小值推出次次小值，以此类推。

结合前面，我们已知最小值 \(a_1+b_1\)，那么关键在于如何找出所有可能候选答案中的最小值，这可以用优先队列实现。

注意 \(a_1+b_2\) 和 \(a_2+b_1\) 同时可以推出 \(a_2+b_2\)，所以注意去重，这可以用 \(set\) 维护二元组实现。

时间复杂度 \(O(n\log n)\).

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

#define PII pair<int,int>
typedef long long LL;
typedef unsigned long long ULL;

LL read() {
    LL sum=0,flag=1; char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') flag=-1; c=getchar();}
    while(c>='0'&&c<='9') {sum=sum*10+c-'0'; c=getchar();}
    return sum*flag;
}

const int N=1e5+10;
int n,a[N],b[N];
struct node {
    int x,y;
    friend bool operator < (node s1,node s2) {
        return a[s1.x]+b[s1.y]>a[s2.x]+b[s2.y];
    }
};
priority_queue<node> q;
set<pair<int,int> > f;

int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++) {
        cin>>b[i];
    }
    int tot=0;
    q.push({1,1}); f.insert({1,1});
    while(q.size()) {
        node t=q.top(); q.pop();

        cout<<a[t.x]+b[t.y]<<' ';
        tot++;
        if(tot==n) break;
        if(t.x+1<=n&&f.count({t.x+1,t.y})==0) {
            q.push({t.x+1,t.y});
            f.insert({t.x+1,t.y});
        }
        if(t.y+1<=n&&f.count({t.x,t.y+1})==0) {
            
            q.push({t.x,t.y+1});
            f.insert({t.x,t.y+1});
        }
    }
    return 0;
}
/*
*/

类似题目：最小函数值，同样是已知最小值，可以推出次小和次次小等的题目。