题目描述

有两个长度都是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 最暴力的方法过了6个点 用贪心方法维护：

#include
        
         using namespace std;//input by bxd#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define repp(i,a,b) for(int i=(a);i>=(b);--i)#define RI(n) scanf("%d",&(n))#define RII(n,m) scanf("%d%d",&n,&m)#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)#define RS(s) scanf("%s",s);#define ll long long#define pb push_back#define REP(i,N)  for(int i=0;i<(N);i++)#define CLR(A,v)  memset(A,v,sizeof A)//#define inf 0x3f3f3f3fconst int N=100000+5;int a[N];int b[N];int heap[N];int from[N];int now[N];void swap1(int a,int b){    swap(heap[a],heap[b]);    swap(from[a],from[b]);}int main(){    int n;    RI(n);    rep(i,1,n)    RI(a[i]);    rep(i,1,n)    RI(b[i]);    rep(i,1,n)    heap[i]=b[1]+a[i],from[i]=i,now[i]=1;    int cnt=1;    while(cnt<=n)    {        printf("%d ",heap[1]);        heap[1]=a[ from[1] ]+b[ ++now[ from[1] ] ];        int no=1;        while( (no<<1)<=n )        {            int nex=no<<1;            if(nex+1<=n&&heap[nex+1]
         
          heap[nex])swap1(no,nex);            else break;            no=nex;        }        cnt++;    }    return 0;}