AcWing 146. 序列
原题链接
简单
作者:
愿愿
,
2024-03-13 19:49:10
,
所有人可见
,
阅读 13
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII; //index, value
const int N = 2010;
int m, n;
int a[N], b[N], c[N];
struct cpm{
bool operator()(const PII a1, const PII a2){
return a1.x > a2.x;
}
};
void merge(){
priority_queue<PII, vector<PII>, cpm> q;
int cnt = 1;
for(int i = 1;i <= n;i++){
q.push({a[1] + b[i], 1});
}
while(cnt <= n){
auto t = q.top();
q.pop();
c[cnt++] = t.x;
q.push({t.x - a[t.y] + a[t.y + 1], t.y + 1});
}
memcpy(a, c, sizeof a);
return;
}
int main(){
int T;
scanf("%d", &T);
while(T--){
scanf("%d%d", &m, &n);
for(int i = 1;i <= n;i++){
scanf("%d", &a[i]);
}
sort(a + 1, a + 1 + n);
while(--m){
for(int i = 1;i <= n;i++){
scanf("%d", &b[i]);
}
merge();
}
for(int i = 1;i <= n;i++) printf("%d ", a[i]);
puts("");
}
return 0;
}