洛谷P1631 序列合并 题解

题目链接：P1631 序列合并

题意：

有两个长度都是N的序列A和B，在A和B中各取一个数相加可以得到$N^2$个和，求这$N^2$个和中最小的N个。

对于100%的数据中，满足1<=N<=100000。

维护一个大根堆，初始有 $N$ 个极大值

贪心地选择较小的 $A_i$ 和较小的 $B_i$ 合并

然后有一个简单易懂的剪枝，具体见代码

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

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)

priority_queue<int> q;
int n,a[N],b[N],c[N],pos;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) cin >> b[i];
    for(int i=1; i<=n; i++) q.push(INF);
    // sort(a+1,a+1+n); sort(b+1,b+1+n);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            int tmp=a[i]+b[j];
            if(tmp<q.top())
            {
                q.pop();
                q.push(tmp);
            }else break;
        }
    }
    while(!q.empty())
    {
        c[++pos]=q.top();
        q.pop();
    }
    for(int i=pos; i>=1; i--)
        cout << c[i] << " \n"[i==1];
    return 0;
}