P1631 序列合并

给你两个1e5的序列问两个序列所有的数合并后总共N^2个数中前N个数的大小
我们先对数组进行排序，得到两个有序的数组AB
之后我们再把A[1]+B[1].A[1]+B[2],…,A[1]+B[N]这样的得出N个有序数列每个数列有N项
接着我们开一个优先队列把这个矩阵中第一列放进去，然后每次拿出最小的后，把那一行后一列加入到优先队列中，最终NlogN解决

#include <bits/stdc++.h>
using namespace std;
#define mk(a,b) make_pair(a,b)
priority_queue<pair<int,int> > q;
int a[100005],b[100005],p[100005];
int main()
{
	int n,cnt=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),p[i]=1;
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++) q.push(mk(-(a[i]+b[1]),i));
	while(q.size()&&cnt<n)
	{
		printf("%d ",-q.top().first);	
		int id=q.top().second;
		q.pop();
		q.push(mk(-(a[id]+b[++p[id]]),id));
		cnt++;
	}
}