多组数据,给定(m)个长度为(n)的序列,从每个序列中取出一个数相加可以得到一个和,输出前n小的和.(n<=2000,m<=100).
分析:某场考试的弱化版,可以在(Tmnlog_n)的时间复杂度内做.考虑(m=2)时的情况,把两个序列都从小到大排序,先把(a[i]+b[1])全都丢入小根堆中,然后每次取出堆顶(a[i]+b[j])记录答案,同时把(a[i]+b[j+1])丢入堆中.
(m>2)时,重复做(m-1)次上述操作即可.具体来说,每次得到的答案当做一个新的(a)序列,然后与读入的(b)序列进行上述操作.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=2005;
int n,m,a[N],b[N],c[N];
struct node{
int x,y,val;
bool operator <(const node &x)const{
return val>x.val;
}
}temp;
inline void solve(){
priority_queue<node>q;
for(int i=1;i<=n;++i){
temp.x=i;temp.y=1;temp.val=a[i]+b[1];
q.push(temp);
}
for(int i=1;i<=n;++i){
temp=q.top();q.pop();
c[i]=temp.val;
if(temp.y<n){
++temp.y;temp.val=a[temp.x]+b[temp.y];
q.push(temp);
}
}
for(int i=1;i<=n;++i)a[i]=c[i];
}
int main(){
int T=read();
while(T--){
m=read(),n=read();
for(int i=1;i<=n;++i)a[i]=read();
sort(a+1,a+n+1);
for(int i=2;i<=m;++i){
for(int j=1;j<=n;++j)b[j]=read();
sort(b+1,b+n+1);solve();
}
for(int i=1;i<n;++i)printf("%d ",a[i]);
printf("%d
",a[n]);
}
return 0;
}