最小的n个和 | ||||||
|
||||||
Description | ||||||
给定A、B两个数列,各包含n个数,分别从A和B中任意取一个数相加得到和,这样会有n^2种结果(包括重复的),求n^2个结果中前n个最小的和。 |
||||||
Input | ||||||
有多组测试数据。 对于每组测试数据,第一行为n,第二行为数列A,第三行为数列B。 1<=n<=100000, 0 <= Ai, Bi <= 10^9。 |
||||||
Output | ||||||
对于每组测试数据,输出一行,包含前n个最小的和,按照升序输出,两数之间用一个空格隔开。 |
||||||
Sample Input | ||||||
5 |
||||||
Sample Output | ||||||
2 3 3 4 4 |
代码
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int a[100005],b[100005],sum[100005];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
for(int i=0;i<n;i++)
scanf("%d",&b[i]);
sort(b,b+n);
for(int i=0;i<n;i++)
sum[i]=b[i]+a[0];
make_heap(sum,sum+n);//建立一个最大堆
for(int i=1;i<n;i++)
for(int j=0;j<n;j++)
{
int temp=a[i]+b[j];
if(temp>=sum[0])
break;
pop_heap(sum,sum+n);///将根元素与最后一个元素调换位置,并对n-1个元素再次进行堆排序
sum[n-1]=temp;
push_heap(sum,sum+n);///将本该入堆的数入堆并进行最大堆排序
}
sort(sum,sum+n);///将前N个数从最大堆中进行从小到大排序,以便下面输出
for(int i=0;i<n-1;i++)
printf("%d ",sum[i]);
printf("%d\n",sum[n-1]);
}
return 0;
}