洛谷P1631 序列合并

题目描述

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

输入格式

第一行一个正整数 $N$；

第二行 $N$ 个整数 $A_{1\dots N}$。

第三行 $N$ 个整数 $B_{1\dots N}$。

输出格式

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

样例 #1

样例输入 #1

3
2 6 6
1 4 8

样例输出 #1

3 6 7

提示

对于 $50\%$ 的数据，$N \le 10^3$。

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1 \le a_i,b_i \le 10^9$。

题解

#include <bits/stdc++.h>
using namespace std;

priority_queue<int, vector<int>, greater<int>> q;
int n, a[100010], b[100010];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    for (int i = 1; i <= n; i++)
        scanf("%d", b + i);
    for (int i = 1; i <= n; i++)
        for (int j = 1; i * j <= n; j++)
            q.push(a[i] + b[j]);
    for (int i = 1; i <= n; i++) {
        printf("%d ", q.top());
        q.pop();
    }
    return 0;
}