题目描述
有两个长度都是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.
【数据规模】
对于50%的数据中，满足1<=N<=1000；
对于100%的数据中，满足1<=N<=100000。
输出格式：输出仅一行，包含N个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。
输入输出样例
思路
a[x]+b[y]<a[x+1]+b[y];
a[x]+b[y]<a[x]+b[y+1];
并且具有紧密性；
所以最开始在优先队列中加入a[1]+b[1](必然是最小的)；
每次取出最小元素a[x]+b[y]输出，并再加入a[x+1]+b[y], a[x]+b[y+1];
!注意判重；
代码实现
1 #include<map> 2 #include<queue> 3 #include<cstdio> 4 const int maxn=1e5+10; 5 int n,a[maxn],b[maxn]; 6 std::map<long long,bool>v; 7 struct nate{ 8 int x,y,z; 9 nate(int a=0,int b=0,int c=0):x(a),y(b),z(c){} 10 }; 11 struct comp{bool operator()(nate a,nate b){return a.z>b.z;}}; 12 int main(){ 13 scanf("%d",&n); 14 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 15 for(int i=1;i<=n;i++) scanf("%d",&b[i]); 16 std::priority_queue<nate,std::vector<nate>,comp>q; 17 q.push(nate(1,1,a[1]+b[1])); 18 int x,y,z; 19 for(int i=1;i<=n;i++){ 20 x=q.top().x,y=q.top().y; 21 printf("%d ",q.top().z),q.pop(); 22 if(!v[(x+1)*maxn+y]&&x+1<=n) 23 q.push(nate(x+1,y,a[x+1]+b[y])),v[(x+1)*maxn+y]=1; 24 if(!v[x*maxn+(y+1)]&&y+1<=n) 25 q.push(nate(x,y+1,a[x]+b[y+1])),v[x*maxn+(y+1)]=1; 26 } 27 return 0; 28 }