洛谷 P1631 序列合并

// 第一反应：把 N² 个和全造出来，排序，取前 N 个
//
// ★ **它不是零分**：题面写着「对于 50% 的数据，N ≤ 10³」——
//   那一档只有 10⁶ 个和，本机 0.07 秒，**稳拿 50 分**。
//   ⇒ 题面那一行分档，就是出题人递过来的暴力档（[第 24 章那条](/sol/p1776/)）。
//
// ⚠ 顶格 N = 10⁵ 就完全不行了：10¹⁰ 个和，光存下来就要 **80 GB**。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    vector<long long> all;
    all.reserve((size_t)n * n);                  // ⚠ 顶格是 10^10 个
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) all.push_back(a[i] + b[j]);
    sort(all.begin(), all.end());

    string out;
    for (int k = 0; k < n; k++) { if (k) out += ' '; out += to_string(all[k]); }
    out += '\n';
    cout << out;
    return 0;
}

// P1631 序列合并 —— ★ 这一版就能 AC：**多路归并**（和隔壁 [P2085] 是同一招）
//
// ============ 先把 N² 个和摆成一张表 ============
//       B₁   B₂   B₃  ...
//   A₁  ·    ·    ·
//   A₂  ·    ·    ·          第 i 行是 A[i] + B[1..N]
//   A₃  ·    ·    ·          ★ 而 B 单调不降 ⇒ **每一行本身就是有序的**
//
//   ⇒ 又是「N 个已经排好序的序列，求前 N 小」——
//     只有每行**当前的头部**有资格当下一个最小值。
//   ⇒ 堆里永远只放 N 个候选（每行一个），取 N 次。O(N log N)。
//
// ⚠ 题面「两个长度为 N 的**单调不降**序列」是命门：
//   一旦 A 或 B 不再有序，「每行的最小值是第一个」就不成立了（第 ⑤ 步量过）。
// ⚠ 1 ≤ Aᵢ, Bᵢ ≤ 10⁹ ⇒ 和最大 2×10⁹ < 2 147 483 647 ⇒ int **够用，余量 7.4%**
//   （和 [P1801](/sol/p1801/) 一模一样的余量）。

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

struct Node {
    long long v;     // A[i] + B[j]
    int i, j;
    bool operator>(const Node& o) const { return v > o.v; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    priority_queue<Node, vector<Node>, greater<Node>> q;
    for (int i = 0; i < n; i++) q.push({a[i] + b[0], i, 0});   // ★ 每行的头部

    string out;
    for (int k = 0; k < n; k++) {
        Node t = q.top();
        q.pop();
        if (k) out += ' ';
        out += to_string(t.v);
        int i = t.i, j = t.j + 1;
        if (j < n) q.push({a[i] + b[j], i, j});                // 那一行往右挪一格
    }
    out += '\n';
    cout << out;
    return 0;
}