给定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 1 3 4 2 0 7 3 5 2 11 10 74 50 47 45 38 64 19 2 84 69 91 46 44 7 67 1 40 60 78 41 Sample Output 2 3 3 4 4 3 9 20 26 39 42 43 45 46 46
代码
#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;}
转载于:https://www.cnblogs.com/13224ACMer/p/4423139.html
