P1631 序列合并

P1631.序列合并

题目描述：

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

输入格式

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

第二行 $N$ 个整数 $A_1,\cdots,A_N$ 。

第三行 $N$ 个整数 $B_1,\cdots,B_N$ 。

输出格式

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

数据范围：

$1\le N \le 10^5, 1\le a_i, b_i, \le 10^9$

题解：

可以看做 $k$ 个有序链表合并。

$a_1 + b_1, a_1 + b_2, \cdots, a_1 +b_n$

$a_2 + b_1, a_2 +b_2, \cdots,a_2 + b_n$

$\ldots$

$a_n + b_1, a_n + b_2, \cdots, a_n + b_n$

先加入一组 $a_i + b_1$

然后每取出一个，就把他的后面一个加入堆中。

代码：

using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int a[maxn], b[maxn];
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    read(n);
    for (int i = 1; i <= n; ++i)
    {
        read(a[i]);
    }
    for (int i = 1; i <= n; ++i)
    {
        read(b[i]);
    }

    priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> q;
    for (int i = 1; i <= n; ++i)
    {
        q.push({a[i] + b[1], i, 1});
    }
    for (int cnt = 1; cnt <= n; ++cnt)
    {
        auto out = q.top();
        auto [sum, indexa, indexb] = out;
        q.pop();
        cout << sum << " ";
        if (indexb + 1 <= n)
            q.push({sum - b[indexb] + b[indexb + 1], indexa, indexb + 1});
    }
    return 0;
}