问题 B: 序列合并

B[0]+A[0] <= B[0]+A[1] <= … <= B[0]+A[N-1]
B[1]+A[0] <= B[1]+A[1] <= … <= B[1]+A[N-1]
……
B[N-1]+A[0] <= B[N-1]+A[1] <= … <= B[N-1]+A[N-1]
显然,在同一列中，每一行都比上面一行的值要大.
因为两个数组都是有序递增，所以先建立堆结构（大顶堆）
将其中一个数组A的第一个元素与另一个数组B的所有元素相加的结果依次放入
然后再从A的第二个元素开始，依次与B中所有元素相加，相加结果与堆中根结点比较
a.如果比堆的根结点小，删除根结点，将此结果加入堆
b.如果比根结点大，那么跳出此次循环，访问A的下一个元素。
最后将大顶堆的数据倒序输出(借助栈进行)

#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

typedef long long ll;
int n;
vector<ll> A, B;
priority_queue<ll> q;

//数组输入函数
void input(vector<ll> &arr, int mode)
{
    ll x;
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &x);
        arr.push_back(x);
        if (mode)
            q.push(B[i] + A[0]);
    }
}
// 堆输出函数
void output(priority_queue<ll> q)
{
    stack<ll> st;
    while (!q.empty())
    {
        st.push(q.top());
        q.pop();
    }
    while (!st.empty())
    {
        printf("%d", st.top());
        st.pop();
        !st.size() ? printf("\n") : printf(" ");
    }
}
int main()
{
    while (~scanf("%d", &n))
    {
        input(A, 0);
        input(B, 1);
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (A[i] + B[j] < q.top())
                {
                    q.pop();
                    q.push(A[i] + B[j]);
                }
                else
                    break;
            }
        }
        output(q);
    }
    return 0;
}