n个最小和

给出两个包含n 个整数的数组 A，B。分别在 A, B 中任意出一个数并且相加，可以得到 n^2个和。求这些和中最小的 n 个。

输入格式:

输入第一行一个整数 n(1≤n≤50000)
接下来一行输入数组 A，用空格隔开。
接下来一行输入数组 B，用空格隔开。
1≤Ai,Bi≤10^9

输出格式:

从小到大输出最小的 n 个和，用空格隔开。

样例输入

4
1 3 5 7
2 4 6 8

样例输出

3 5 5 7

考察核心:

1. 优先队列的经典应用
2. 重载优先队列

解题思路：

1. 首先我们把这两个数组A，B排序。
2. 把{A[1~n]+b[1]，A的下标，B的下标}入队
3. 我们将优先队列的优先顺序依照结构体中的sum排序
4. 将优先级最大的出队例如：{A[a]+B[b],a,b}
5. 则下一次入队就是{A[a]+B[b+1],a,b+1}
6. 重复n次，即两个集合中各选一个数组成最小的n个和。

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
struct n{
    int sum;
    int posa;
    int posb;
    bool operator <(const n &a)const{
        return sum>a.sum;
    }//优先队列中自定义优先级排序
};
int main(){
    int n;
    cin>>n;
    int a[50001],b[50001];
    for(int i=1;i<=n;++i)   cin>>a[i];
    for(int i=1;i<=n;++i)   cin>>b[i];

    sort(a+1,a+n+1);
    sort(b+1,b+n+1);//别忘记n是从1开始，因此end()要多加上1。
    priority_queue<struct n> v;

    for(int i=1;i<=n;++i){//将集合a[1~n]+b[1]放入优先队列
        struct n tmp;
        tmp.sum=a[i]+b[1];
        tmp.posa=i;
        tmp.posb=1;
        v.push(tmp);
    }
    
    struct n tmp=v.top();//输出第一个不加空格的数
    cout<<tmp.sum;
    v.pop();
    tmp.sum=a[tmp.posa]+b[++tmp.posb];
    v.push(tmp);
    
    for(int i=2;i<=n;++i){//为了最后一个不多一个空格，采用" "x形式
        struct n tmp=v.top();
        cout<<" "<<tmp.sum;
        v.pop();
        tmp.sum=a[tmp.posa]+b[tmp.posb+1];//将a[i]+b[j+1]放入优先队列
        tmp.posb+=1;
        v.push(tmp);
    }
}