AcWing 146. 序列
原题链接
简单
作者:
geats兔
,
2024-04-07 19:40:55
,
所有人可见
,
阅读 1
C++ 代码
#include<iostream>
using namespace std;
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
const int N=2010;
int a[N],b[N],c[N];
int 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({a[0]+b[i],0});
int j=0;
while(heap.size()&&j<n)
{
auto t=heap.top();
heap.pop();
c[j]=t.first;
int idx=t.second;
heap.push({c[j]-a[idx]+a[idx+1],idx+1});
j++;
}
memcpy(a,c,sizeof c);
}
int main()
{
int T;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++)
{
for(int i=0;i<n;i++) cin>>b[i];
merge();
sort(a,a+n);
}
for(int i=0;i<n;i++) cout<<a[i]<<" ";
cout<<endl;
}
return 0;
}