算法1
(多路归并 + 优先队列) $O(n^2)$
//合并a[] 和 b[]
// 分组 , 分成n组 :
// b1 + a1 ,b1+a2,b1+a3,....,b1+an;
// b2+a1,b2+a2,b2+a3,......b2+an
// ........
// bn+a1,bn+a2,......bn+an
// a排好序 , 所以每一组内部都是排好序的 , 所以每一组第一个数一定是最小值
// 假设最小的数是(b1+a1),那么第一组中最小的数就会变成b1+a2,循环往复,取n个当前最小的即可
// 用c[i]临时存放最小的数
// 优先队列每次只存当前每组中最小的数
// 每次取出队头 , 然后将这一组的下一个数加入队列中
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef pair<int, int> PII;
const int N = 2e3+10;
int a[N] , b[N] , c[N] ;
int m , n ;
// 每次将两个合并
void msort(){
//合并a[] 和 b[]
// 分组 , 分成n组 :
// b1 + a1 ,b1+a2,b1+a3,....,b1+an;
// b2+a1,b2+a2,b2+a3,......b2+an
// ........
// bn+a1,bn+a2,......bn+an
// a排好序 , 所以每一组内部都是排好序的 , 所以每一组第一个数一定是最小值
// 假设最小的数是(b1+a1),那么第一组中最小的数就会变成b1+a2,循环往复,取n个当前最小的即可
// 用c[i]临时存放最小的数
// 优先队列每次只存当前每组中最小的数
// 每次取出队头 , 然后将这一组的下一个数加入队列中
priority_queue<PII , vector<PII> , greater<PII> > q ;
for(int i=0;i<n;i++) q.push({a[0]+b[i],0}) ;// 先将每一组第一个数放进去
for(int i=0;i<n;i++){
auto it = q.top() ; q.pop() ;
int xx = it.first ; int idx = it.second ;
c[i] = xx ;
int y = xx - a[idx] + a[idx+1] ;
q.push({y,idx+1});
}
memcpy(a, c, sizeof 4 * n);
}
inline void solve(){
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++){
for(int j=0;j<n;j++) cin >> b[j] ;
msort() ;
}
for(int i=0;i<n;i++) cout << a[i] << " " ;
cout << endl ;
}
signed main(){
IOS
int _ = 1 ; cin >> _; while(_ --) solve();return 0;
}