P1631 序列合并 【序列堆合并】

P1631 序列合并 【序列堆合并】
题目描述
有两个长度为 N 的单调不降序列 A,B，在 A,B 中各取一个数相加可以得到 N^2  个和，求这 N^2  个和中最小的 N 个。
输入格式
第一行一个正整数 N；
第二行 N 个整数 A1…N。
第三行 N 个整数 B1…N。
输出格式
一行 N 个整数，从小到大表示这 N 个最小的和。
输入输出样例
输入 #1
3
2 6 6
1 4 8
输出 #1
3 6 7
说明/提示
对于 50% 的数据，N≤10^3。
对于 100% 的数据，1 ≤ N ≤ 10^5 ，1 ≤ ai,bi≤ 10^9 。

以下使用序列堆合并的解题思路：
先把A和B两个序列分别从小到大排序，变成两个有序队列。
然后，从A和B中各任取一个数相加得到N^2个和，可以把这些和看成形成了n个有序队列：
A[1]+B[1] <= A[1]+B[2] <= … <= A[1]+B[N]
A[2]+B[1] <= A[2]+B[2] <= … <= A[2]+B[N]
……
A[N]+B[1] <= A[N]+B[2] <= … <= A[N]+B[N]
要将这N个有序队列进行合并排序：
1. 将这N个队列中的第一个元素放入一个堆中；
2. 每次取出堆中的最小值。若这个最小值来自于第k个队列，那么，就将第k个队列的下一个元素放入堆中。
时间复杂度：O(NlogN)。

#include 
using namespace std;
const int N=1e5+10;
long long a[N],b[N],id[N];
int main()
{	
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	priority_queueint,int>,vectorint,int>>, greaterint,int>>> q;
	for(int i=1;i<=n;i++){
		cin>>b[i];
		id[i]=1;//记录a的下标
		q.push({a[1]+b[i],i});//b[i]和a[1]的和
	}
	while(n--){
		cout<top().first<<" ";
		int i=q.top().second;
		q.pop();
		q.push({a[++id[i]]+b[i],i});//b[i]和a的下一个元素的和
	}
    return 0;
}