C++ 代码

/*
    给定m*n个数，没次从每行取一个数，共取m个 相加 求最小的前n个数

    m行 --> 每次取两行 操作m-1次 
    问题简化为： 
    两行 每行n个数， 从每行取一个数， 使和最小 
     将第一行的n个数排序， 之后将第一行的每个数和第二行相加， 得到 n行 每行n个数的序列  最小的数字一定在第一行 
*/

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N = 2e3 + 10;

int a[N], b[N], c[N];
int T,n, m;
typedef pair<int,int> pII;

void merge(){
    priority_queue<pII, vector<pII>, greater<pII>> heap; //小根堆  第一个存数的值， 第二个记录哪一列往下 即下标 

    for(int i = 0; i < n; i++){ //将第一行（包含最小的那个数）  进堆 
        heap.push({b[i] + a[0], 0});
    }

    for(int i = 0 ; i < n; i++){
        pII p = heap.top(); //存最小的那个元素 
        heap.pop(); //删除最小元素  
        c[i] = p.first; //将最小元素的值 存到c数组 
        heap.push({p.first - a[p.second] + a[p.second + 1], p.second+1}); //将删除那个元素列的下一个最小的入堆 
    }

    for(int i = 0; i < n; i++) a[i] = c[i];
}

int main(){
    cin >> T;
    while(T--){
        cin >> m >> n;

        for(int i = 0; i < n; i++) cin >> a[i];
        sort(a,a+n); //将第一行数组 排序 

        for(int i = 0; i < m-1; i++){ //执行 m-1 次 二路归并 
            for(int j = 0; j < n; j++){
                cin >> b[j];
            }

            merge(); //将a[]、b[]合并 并将结果存在a[]中 
        } 

        for(int i = 0; i < n; i++) cout << a[i] << " " ; //输出前n小的数字 
        puts("");
    }

    return 0;
}