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

 

输入输出格式

输入格式：

第一行一个正整数N；

第二行N个整数A_iAi​, 满足A_i\le A_{i+1}Ai​≤Ai+1​且A_i\le 10^9Ai​≤109;

第三行N个整数B_iBi​, 满足B_i\le B_{i+1}Bi​≤Bi+1​且B_i\le 10^9Bi​≤109.

【数据规模】

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

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

输出格式：

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

输入输出样例

输入样例#1： 

32 6 61 4 8

输出样例#1： 

3 6 7

很显然我们有 a和b两个数组 。很显然我们要用一个 c数组存和 。很显然要用heap堆排(实际上是只用了向下维护操作)。

我们的c[ i ][ j ]，用来存储a中第i个数分别和b中的所有数相加得到的结果。很显然 会 爆空间，所以等下会有优化。

 

for (int i = 1;i <= n;i++)            for (int j = 1;j <= n;j++)                c[i][j] = a[i]+b[j];

依题意得：a是有序数列，b也是有序数列，则对于任意c[ i ]也会是一个有序数列。那么我们就把c[ i ]的第一个数存入heap。

for (int i = 1;i <= n;i++) 　　heap[i] = c[i][j];

然后维护一下heap

while（没有输出够n个数）{    输出；    放入 堆顶数所在的数组的下一个数    维护}

优化：

首先我们知道，heap[ i ]只需要用一个值，那我们可不可以在heap需要的时候再把c[ i ][ j ]算出来呢？

然后我们发现 c[ i ][ j ] = a[ i ]+b[ j ]中i相当于目前对顶数所在的数组，j就表示下一个数的下标。

于是优化就出来了。

for (int i = 1;i <= n;i++) heap[i] = a[i]+b[1]     ……    int t = from[1];    step[t]++;    heap[1]=a[t] + b[ step[t] ];

代码：

#include
              
               using namespace std;int a[100000],b[100000],heap[100000],from[100000],step[100000],n,sum=1;void swap(int x,int y)//手打swap交换，同时交换来源数组。{    int k = heap[x];    heap[x] = heap[y];    heap[y] = k;    k = from[x];    from[x] = from[y];    from[y] = k;}int main(){    scanf("%d",&n);    for (int i = 1;i <= n;i++) scanf("%d",&a[i]);    for (int i = 1;i <= n;i++) scanf("%d",&b[i]);    for (int i = 1;i <= n;i++) heap[i] = a[i]+b[1],from[i] = i,step[i] = 1;     //这一步就是优化。把c去掉了，取而代之的是现做现卖的合成。    while (sum <= n)    {        printf("%d ",heap[1]);        int t = from[1];        step[t]++;        heap[1]=a[t] + b[ step[t] ];//现做现卖的合成。        int x = 1,s;        while (x<<1 <= n)//经典的下传        {            s = x<<1;            if (heap[s] > heap[s + 1] && s + 1 <= n) s++;            if (heap[x] > heap[s])            {                swap(x,s);                x = s;              }else break;        }        sum++;      }    return 0;}