【题目描述】：

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

【输入描述】：

第一行一个正整数N；

第二行N个整数Ai,满足Ai<=Ai+1且Ai<=10^9;

第三行N个整数Bi,满足Bi<=Bi+1且Bi<=10^9.

【输出描述】：

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

【样例输入】：

3 2 6 6 1 4 8

【样例输出】：

3 6 7

【时间限制、数据范围及描述】：

时间：1s 空间：128M

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

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

代码

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<queue> using namespace std; int n,a[100005],b[100005],c[100005]; struct aaa{ int d,s; }; bool operator >(const aaa &a,const aaa &b){ return a.s>b.s; } priority_queue<aaa,vector<aaa>,greater<aaa> >q; int main() { scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); c[i]=1; } for(int i=1;i<=n;i++){ scanf("%d",&b[i]); } sort(b+1,b+1+n); for(int i=1;i<=n;i++){ q.push((aaa){i,a[i]+b[c[i]]}); } for(int i=1;i<=n;i++){ printf("%d ",q.top().s); aaa h=q.top(); c[h.d]++;q.pop(); q.push((aaa){h.d,a[h.d]+b[c[h.d]]}); } return 0; } 

此题只能够用堆做，试了别的方法，但无果...