序列合并

题目描述

有两个长度为 N 的单调不降序列 A,B，在 A,B 中各取一个数相加可以得到  个和，求这  个和中最小的  个。

输入格式

第一行一个正整数 N；

第二行 N 个整数 1…N​。

第三行 N 个整数 1…N​。

输出格式

一行 N 个整数，从小到大表示这 N 个最小的和。

样例输入

3
2 6 6
1 4 8

样例输出

3 6 7

参考代码

#include 
#define ll long long
using namespace std;
 
priority_queue q;
stack  st;
 
const int N = 1e5 + 5;
int a[N], b[N];
 
int main()
{
	int n;
	cin>>n;
	
	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);
		
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			ll h = a[i] + b[j];
			if(q.size() < n)
				q.push(h);
			else
			{
				if (q.top() < h)
					break;
				q.push(h);
				q.pop();
			}
		}
	}
	
	for(int i = 1; i <= n; i++)
	{
		st.push(q.top());
		q.pop();
	}	
	
	while(!st.empty())
	{
		cout<top()<<" ";
		st.pop();
	}
	
	return 0;
}