1245 最小的N个和

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题目描述 Description

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

输入描述 Input Description

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

输出描述
Output Description

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

样例输入
Sample Input

1 3 2 4 5
6 3 4 1 7

样例输出
Sample Output

2 3 4 4 5

数据范围及提示
Data Size & Hint

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

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #define M 100010

 using namespace std;

 int a[M],b[M],heap[M],l=;

 int put(int d)  //建立堆并维护

 {

     heap[++l]=d;

     int next,now=l;

     while(now>)

     {

         next=now/;

         if(heap[now]<=heap[next])break;

         swap(heap[now],heap[next]);

         now=next;

     }

 }

 int get()  //删除堆顶元素

 {

     int now,next;

     heap[]=heap[l--];

     now=;

     while(now*<=l)

     {

         next=now*;

         if(next<l&&heap[next]<heap[next+])next++;

         if(heap[now]>=heap[next])break;

         swap(heap[now],heap[next]);

         now=next;

     }

 }

 int main()

 {

     int n;

     scanf("%d",&n);

     for(int i=;i<=n;i++)

         scanf("%d",&a[i]);

     for(int i=;i<=n;i++)

         scanf("%d",&b[i]);

     sort(a+,a+n+);  //排序

     sort(b+,b+n+);

     heap[]=(a[]+b[]);

     for(int i=;i<=n;++i)

         put(a[]+b[i]);  //初始化

     for(int i=;i<=n;i++)

     {

         if(a[i]+b[]>=heap[])break;  //因为a,b，都是递增的，所以 a[i]+b[1]>=heap[1]，以后的a会更大；

         for(int j=;j<=n;j++)

         {

             if(a[i]+b[j]>=heap[])continue; //因为a,b，都是递增的，所以 a[i]+b[j]>=heap[1]，以后的b会更大；

             put(a[i]+b[j]);

             get();  //删除最大的，留下n个数

         }

     }

     sort(heap+,heap+n+);  //从小到大排序

     for(int i=;i<=n;++i)  //输出

         printf("%d ",heap[i]);

     return ;

 }