# [题解] Luogu 1631 – 序列合并

## 样例输入

3
2 6 6
1 4 8


## 样例输出

3 6 7


## 解题思路

\begin{aligned} A_1 + B_1 \leq A_1 + B_2 & \leq \cdots \leq A_1 + B_n \\ A_2 + B_1 \leq A_2 + B_2 & \leq \cdots \leq A_2 + B_n \\ \cdots \\ A_n + B_1 \leq A_n + B_2 & \leq \cdots \leq A_n + B_n \\ \end{aligned}

## 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define P pair<int, int>

using namespace std;
const int MAXN = 100000 + 10;

int x = 0;
int p = 1;
char ch = getchar();

while(ch < '0' || ch > '9'){
if(ch == '-')
p = 0;
ch = getchar();
}

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}

return p ? x : (-x);
}

int n;
int A[MAXN], B[MAXN], pos[MAXN];

priority_queue<P, vector<P>, greater<P> >que;
int main(){

for(register int i=1; i<=n; i++){
}

for(register int i=1; i<=n; i++){
}

sort(A+1, A+n+1);
sort(B+1, B+n+1);

for(register int i=1; i<=n; i++){
pos[i] = 1;
que.push(make_pair(A[i] + B[1], i));
}

for(register int i=1; i<=n; i++){
P front = que.top();
printf("%d ", front.first);
que.pop();

que.push(make_pair(A[front.second]+B[++pos[front.second]], front.second));
}

return 0;
}