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

第一行输入一个正整数N；第二行N个整数Ai 且Ai≤10^9；第三行N个整数Bi，
且Bi≤10^9

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

5

1 3 2 4 5 
6 3 4 1 7

2 3 4 4 5

【数据规模】 对于 100%的数据，满足 1≤N≤100000。

此题做法等同于洛谷1631序列合并

#include <algorithm> #include <cstdio>#include <stack>using namespace std;stack<int>stac;int size,n,i,j,a[100000],heap[100000],b[100000];inline void push(int a){    heap[++size]=a;    int pos=size;    while(pos>1)    {        int next=pos/2;        if(heap[next]>heap[pos]) break;        swap(heap[next],heap[pos]);        pos=next;    }}inline void down(){    int pos=1;    while(pos*2<=size)    {        int next=pos*2;        if(heap[next+1]>heap[next])        next++;        if(heap[next]<heap[pos]) break;        swap(heap[pos],heap[next]);        pos=next;    }}inline void pop(){    heap[1]=heap[size--];    int pos=1;    while(pos*2<=size)    {        int next=pos*2;        if(heap[next+1]>heap[next]) next++;        if(heap[next]<heap[pos]) break;        swap(heap[next],heap[pos]);        pos=next;    }}int main(){    scanf("%d",&n);    for(i=0;i<n;++i)    scanf("%d",&a[i]);    for(i=0;i<n;++i)    scanf("%d",&b[i]);    sort(a,a+n);    sort(b,b+n);    for(i=0;i<n;++i)    {        for(j=0;j<n;++j)        {            if(size<n)            push(a[i]+b[j]);            else            {                int Another=a[i]+b[j];                if(Another<heap[1])                {                    heap[1]=Another;                    down();                }                else break;//剪枝            }        }    }    for(i=0;i<n;++i)    {        stac.push(heap[1]);        pop();    }    while(!stac.empty())    {        printf("%d ",stac.top());        stac.pop();    }    return 0;}