推荐博客:http://t.csdn.cn/zZusQ
解题思路:
1:首先我们思考如何将两个序列合并,假如有两个序列a[n], b[n], 如下:
{
1: a1, a2, a3, ...., an;
2: b1, b2, b3, ....., bn;
先将a[n]排序, 则所有在a[n], b[n]中任意挑选两个数,他们的和为:
b1 + a1, b1 + a2, b1 + a3, ...., bn + an;
b2 + a1, b2 + a2, b2 + a3, ...., b2 + an;
.
.
.
bn + a1, bn + a2, bn + a3, ...., bn + an;
因为a[n]是从小到大排列的所以第一列肯定是最小的数,
然后我们需要每次选择最小第一列中最小的数,假设第一列中
b1 + a1 最小那么下次我们要从b1 + a2, b2 + a1, b3 + a1, ..., bn + a1中选择一个最小的数,
将这个最小的数记录到c[n]中,最后c[n]即是这两排合并的最小的数,且是从小到大排序的,
然后再将c[n]都记录到a[n], 再次重复上面的操作m - 1次,即最后a[n]记录的就是最小的前n个数
}
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 2010;
int m, n;
int a[N], b[N], c[N];
void merge()
{
priority_queue<PII, vector<PII>, greater<PII>> heap;
for (int i = 0; i < n; i ++ ) heap.push({a[0] + b[i], 0});//第一个存两数和,第二个存的是下标
for (int i = 0; i < n; i ++ )
{
auto t = heap.top();//每次取出每一列的最小和
heap.pop();
c[i] = t.first;
heap.push({t.first - a[t.second] + a[t.second + 1], t.second + 1});//将下一个数读入
}
memcpy(a, c, sizeof 4 * n);
}
int main()
{
int T;
cin >> T;
while (T -- )
{
scanf("%d %d", &m, &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
sort(a, a + n);
for (int i = 0; i < m - 1; i ++ )
{
for (int j = 0; j < n; j ++ ) scanf("%d", &b[j]);
merge();
}
for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);
puts("");
}
return 0;
}