序列合并

序列合并"/>

序列合并

题目描述

有两个长度为 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 <bits/stdc++.h>
#define ll long long
using namespace std;priority_queue<ll> q;
stack <ll> 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<<st.top()<<" ";st.pop();}return 0;
}