前 \(k\) 小数
题目：
有两个长度为 \(n\) 的数列 \(a, b, (1\leq i, j\leq n)\) ，通过 \(a_i+b_j\) 可以构造出 \(n\times n\) 个数，求构造出的数中前 \(k\) 小的数。
格式：
输入格式：
第一行 \(2\) 个数 \(n, k\)；
第二行 \(n\) 个数，表示数列 \(a\)；
第三行 \(n\) 个数，表示数列 \(b\)。
其中：\(1 \leq n \leq 1e4, 1\leq k \leq n \times n \leq 1e4, 1 \leq a_i, b_j \leq 1e6\)
输出格式：
从小到大输出前 \(k\) 小的数。
样例：
输出：
3 3
2 6 6
1 4 8
输出：
3 6 7
思路：
将第一行和第二行的元素按大小排序，假设用 \(n\times n\) 矩阵 \(M_{ij}\) 表示 \(a_i+b_j\) ，矩阵中，右边的元素一定比左边大，上面的元素一定比右边大，首先把矩阵的第一列元素放入最小堆里，每次询问时，取堆顶，并把堆顶元素的右边一个元素入堆，直至完成。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e8 + 7;
int m, k, a[N], b[N];
struct NODE {
int ida, idb, num;
bool operator>(const NODE &a) const {
return num > a.num;
}
} temp;
// 优先队列
priority_queue<NODE, vector<NODE>, greater<NODE>> q;
int main() {
cin >> m >> k;
for (int i = 1; i <= m; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
cin >> b[i];
}
sort(a + 1, a + m + 1);
sort(b + 1, b + m + 1);
for (int i = 1; i <= m; i++) {
q.push({i, 1, a[i] + b[1]});
}
for (int i = 1; i <= k; i++) {
temp = q.top();
q.pop();
cout << temp.num << " ";
temp.num = a[temp.ida] + b[++temp.idb];
q.push(temp);
}
return 0;
}
前 \(k\) 小数（进阶）
题目：
给你 \(n\) 个长度为 \(m\) 的已知数列，你一次可以从每个数列中选出一个元素，共 \(n\) 个数，将这 \(n\) 个数的和，放入 \(a\) 数组中，穷举所有的选数可能，并且都放入 \(a\) 数组中。请你计算 \(a\) 数列中前 \(k\) 小数是多少？
格式：
输入格式：
输入 \(n, m, k\)；
接下来 \(n\) 行，每一行 \(m\) 个数，空格分隔，一行表述一个数列，共 \(n\) 行。
其中：\(1\leq n\leq 200, 1\leq k\leq m\leq 200\)
输出格式：
从小到大输出前 \(k\) 小的数。
样例：
输入：
2 2 2
1 2
1 2
输出：
2 3
思路：
将二维数组中每一行的所有元素相加，并将结果保存在一个一维数组中。首先读入二维数组的大小和值，然后对于第一行的所有元素，将其加入一维数组 b 中。然后从第二行开始遍历二维数组，对于每个元素，遍历一维数组 b 中的元素，将其加上当前元素，并将结果存入一个新的一维数组 c 中。在遍历完一维数组 b 后，将一维数组 c 按照从小到大的顺序排序，并取出其中前 m 个元素，更新一维数组 b。最后，再将一维数组 b 按照从小到大的顺序排序，并输出前 k 个元素。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e8 + 7;
int n, m, k, a[N], b[N], c[N];
struct NODE {
int ida, idb, num;
bool operator>(const NODE &a) const {
return num > a.num;
}
} temp;
priority_queue<NODE, vector<NODE>, greater<NODE>> q;
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
cin >> b[i];
}
sort(a + 1, a + m + 1);
sort(b + 1, b + m + 1);
for (int i = 1; i <= m; i++) {
q.push({i, 1, a[i] + b[1]});
}
for (int i = 1; i <= k; i++) { // c中放a和b中前k小的数
temp = q.top();
q.pop();
c[i] = temp.num;
temp.num = a[temp.ida] + b[++temp.idb];
q.push(temp);
}
n -= 2;
while (n--) {
while (!q.empty()) { // 清空队列
q.pop();
}
for (int i = 1; i <= k; i++) {
a[i] = c[i];
}
for (int i = 1; i <= m; i++) {
cin >> b[i];
}
sort(b + 1, b + m + 1);
for (int i = 1; i <= k; i++) {
q.push({i, 1, a[i] + b[1]});
}
for (int i = 1; i <= k; i++) {
temp = q.top();
q.pop();
c[i] = temp.num;
temp.num = a[temp.ida] + b[++temp.idb];
q.push(temp);
}
}
for (int i = 1; i <= k; i++) {
cout << c[i] << " ";
}
return 0;
}