单走一个代码+注释
C++ 代码
/*
最小的序列和
多路归并:求前n大的数字(用归并的思想每次把两个区间合成一个区间)
一开始的思路是首先把每一个序列都排好序,然后再一个一个取,但是后来发现如果每个序列排好序然后一个一个弹出差值最小的那个不能遍历到每一种情况(所有的情况是n的m次方,而我这样一个一个弹出只有n*m种情况)
最后正解的思路是每次把两个数组合并在一起,假设为a[n],b[n]那么显然a[i]+b[i]有n*n种情况(O(n²)),但是我只需要求最小的n个值(O(nlogn))
所以这最小的n个序列和的值肯定是在a[n]+b[n]的前n小的数中取到
反证:假如不在答案的前n个序列和当中的一个a[n]+b[n]不是在a[n]+b[n]的前n小的数取到,那么一定可以在a[n]+b[n]的前n小的数中把这个数替换掉
所以每次合并两个数组,合并的到的区间再往下合并下面的数组,最后得到的一个长度为n的数组就是答案
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define int long long
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int N=2020,M=1010,INF=4e18;
int n,m;
//priority_queue<int,vector<int>,greater<int>>p[N];
int a[N],c[N],b[N];
typedef pair<int,int> PII;
void merge()
{
priority_queue<PII,vector<PII>,greater<PII>>p;
for(int j=0;j<n;j++)p.push({a[0]+b[j],0});
for(int j=0;j<n;j++)
{
auto t=p.top();
p.pop();
c[j]=t.fi;
p.push({t.fi-a[t.se]+a[t.se+1],t.se+1});
}
for(int j=0;j<n;j++)a[j]=c[j];
return;
}
void solve()
{
cin>>m>>n;
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
for(int i=1;i<m;i++)
{
for(int j=0;j<n;j++)cin>>b[j];
// cout<<"yes"<<endl;
merge();
}
for(int i=0;i<n;i++)cout<<a[i]<<" ";
cout<<endl;
}
signed main()
{
IOS;
int T=1;
cin>>T;
while(T--)
solve();
return 0;
}