C++(g++ 7.5.0) 解法, 执行用时: 36ms, 内存消耗: 504K, 提交时间: 2023-07-28 20:03:34

#include<bits/stdc++.h>
using namespace std;
long long t,a[1000001],m,n,b[1000001],c[1000001];
inline void merge(){
	priority_queue<pair<long long,long long>,vector<pair<long long,long long> >,greater<pair<long long,long long> > >q;
	for(register int i=1;i<=n;++i)q.push({a[1]+b[i],1});
	for(register int i=1;i<=n;++i){
		long long s=q.top().first,p=q.top().second;q.pop();
		c[i]=s;q.push({s-a[p]+a[p+1],p+1});
	}
	for(register int i=1;i<=n;++i)a[i]=c[i];
}
int main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld",&m,&n);
		for(register int i=1;i<=n;++i)scanf("%lld",&a[i]);
		sort(a+1,a+n+1);--m;
		while(m--){
			for(register int i=1;i<=n;++i)scanf("%lld",&b[i]);
			merge(); 
		}
		for(register int i=1;i<=n;++i)printf("%lld ",a[i]);
		puts("");
	}
}

C++14(g++5.4) 解法, 执行用时: 55ms, 内存消耗: 484K, 提交时间: 2020-06-06 13:23:33

#include<bits/stdc++.h>
using namespace std;
const int M=1001,N=2010;
typedef pair<int,int> pii;
int a[N],b[N],c[N],m,n,t;

void merge()
{
	priority_queue<pii,vector<pii>,greater<pii> > h;
	for(int i=0;i<n;i++)
	h.push({a[0]+b[i],0});
	for(int i=0;i<n;i++)
	{
		auto t=h.top();
		h.pop();
		int s=t.first,p=t.second;
		c[i]=s;
		h.push({s-a[p]+a[p+1],p+1});
	}
	for(int i=0;i<n;i++)
	a[i]=c[i];
}
int main()
{
	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);
	    for(int i=1;i<m;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;
}

C++ 解法, 执行用时: 158ms, 内存消耗: 480K, 提交时间: 2021-12-25 20:16:40

#include<bits/stdc++.h>
using namespace std;
int m,n,t,a[2001],b[2001];
priority_queue<int,vector<int>,less<int> >qq;
int main(){
    cin>>t;
    while(t--){
    	cin>>m>>n;
        m--;
        for(int i=0;i<n;i++)cin>>a[i];
        sort(a,a+n);
        while(m--){
            for(int i=0;i<n;i++)cin>>b[i],qq.push(a[0]+b[i]);
            sort(b,b+n);
            for(int i=1;i<n;i++)for(int j=0;j<n;j++){if(a[i]+b[j]>qq.top())break;qq.pop();qq.push(a[i]+b[j]);}
            for(int i=n-1;i>-1;i--)a[i]=qq.top(),qq.pop();
        }
        for(int i=0;i<n;i++)cout<<a[i]<<" ";
        cout<<"\n";
    }
    return 0;
}