算法题：序列合并

问题描述

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

输入格式

第一行一个正整数N(1<=N<=100000)；

第二行N个整数Ai,满足 Ai​≤Ai+1​且Ai​<=10^9;

第三行N个整数Bi​, 满足Bi​≤Bi+1​且Bi​<=10^9.

输出格式

输出仅一行，包含N个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。

样例

输入

3
2 6 6
1 4 8

输出

3 6 7

数据范围

对于50%的数据中，满足1<=N<=1000；

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

解决方案

思路

二叉堆

代码

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct cmp {
    bool operator()(int a, int b) {
        return a > b;//小根堆
    }
};

priority_queue<int, vector<int>, cmp> q;//小根堆

int main() {
    int n;
    cin >> n;

    int arr[100000];
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    for (int i = 0; i < n; ++i) {
        int t;
        cin >> t;
        for (int j = 0; j < n; ++j) {
            q.push(t + arr[j]);
        }
    }

    for (int i = 0; i < n; ++i) {
        cout << q.top() << " ";
        q.pop();
    }

    return 0;
}