多路归并法
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 2010;
int n, m;
int a[N], b[N], c[N]; //c为临时数组,储存每两组数的前n个最小值
void merge()
{
priority_queue<PII, vector<PII>, greater<PII>> heap; //heap的第二个值表示当前用到了第几个数
for (int i = 0; i < n; i ++ ) heap.push({b[i] + a[0], 0}); //初始化为b对应a[0]的值
for (int i = 0; i < n; i ++ )
{
auto p = heap.top();
heap.pop();
c[i] = p.x;
//下一步将{(b[i] + a[k]), k} 变成 {(b[i] + a[k + 1]), k + 1}
heap.push({p.x - a[p.y] + a[p.y + 1], p.y + 1}); //求b对应a[i](即a的下一元素)的值
}
memcpy(a, c, sizeof a); //把c中元素拷贝到a
}
int main()
{
int T;
scanf("%d", &T);
while (T -- )
{
scanf("%d%d", &m, &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
sort(a, a + n); //排序后a[0]为a中最小元素
for (int i = 0; i < m - 1; i ++ ) //m组测试用例
{
for (int j = 0; j < n; j ++ ) scanf("%d", &b[j]); //每组n个数
//你可能会问,为什么不把b也排序,这样最小加最小不就是最最小了吗?
//仔细想想其实排不排都一样,时间复杂度不变的,所以干脆就不排了。
//sort(b, b + n);
merge();
}
//打印拷贝过来的值,开始下一轮循环后会覆盖掉a当前值
for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);
puts("");
}
return 0;
}