【题目来源】
洛谷：P1631 序列合并 - 洛谷
【题目描述】
有两个长度为 N 的单调不降序列 \(A,B\)，在 \(A,B\) 中各取一个数相加可以得到 \(N^2\) 个和，求这 \(N^2\) 个和中最小的 \(N\) 个。
【输入】
第一行一个正整数 \(N\)；
第二行 \(N\) 个整数 \(A_{1\dots N}\)。
第三行 \(N\) 个整数 \(B_{1\dots N}\)。
【输出】
一行 \(N\) 个整数，从小到大表示这 \(N\) 个最小的和。
【输入样例】
3
2 6 6
1 4 8
【输出样例】
3 6 7
【算法标签】
《洛谷 P1631 序列合并》 #二分# #堆# #排序#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int MAX_N = 100005; // 定义数组最大长度
int n; // 数组长度
int a[MAX_N], b[MAX_N]; // 存储两个输入数组
int id[MAX_N]; // id[i]记录b[i]当前配对的a数组下标// 定义小根堆，存储<两数和, b数组下标>
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;int main()
{// 输入数组长度cin >> n;// 输入数组afor (int i = 1; i <= n; i++)cin >> a[i];// 输入数组bfor (int i = 1; i <= n; i++)cin >> b[i];// 初始化id数组和优先队列for (int i = 1; i <= n; i++){id[i] = 1; // 初始每个b[i]与a[1]配对q.push({a[1] + b[i], i}); // 将初始配对和存入队列}// 输出前n小的两数和while (n--){// 获取当前最小的两数和cout << q.top().first << " ";// 获取对应的b数组下标int i = q.top().second;q.pop();// 将该b[i]与a的下一个元素配对id[i]++;q.push({a[id[i]] + b[i], i});}return 0;
}
【运行结果】
3
2 6 6
1 4 8
3 6 7