AcWing 146. 序列Java版
原题链接
简单
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int []a,b,c;
static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t=Integer.parseInt(br.readLine());
while(t-->0){
String[] s = br.readLine().split(" ");
int m=Integer.parseInt(s[0]);
n=Integer.parseInt(s[1]);
a=new int[n+2];
b=new int[n+1];
String[] s1 = br.readLine().split(" ");
for(int i=1;i<=n;i++) a[i]=Integer.parseInt(s1[i-1]);
Arrays.sort(a, 1,n+1);
for(int i=1;i<m;i++){
String[] s2 = br.readLine().split(" ");
for(int j=1;j<=n;j++) b[j]=Integer.parseInt(s2[j-1]);
merge(a,b);
}
for(int i=1;i<=n;i++) System.out.print(a[i]+" ");
System.out.println();
}
}
private static void merge(int[] a, int[] b) {
//for(int i=1;i<=n;i++) System.out.print(b[i]+" ");
c=new int[n+1];
PriorityQueue<node> deq=new PriorityQueue<>(new Comparator<node>() {
@Override
public int compare(node o1, node o2) {
return o1.x-o2.x;
}
});
for(int i=1;i<=n;i++){
node no=new node(a[1]+b[i],1);
deq.add(no);
}
for(int i=1;i<=n;i++){
node t=deq.peek();
c[i]=t.x;
deq.poll();
if(t.y+1<=n) deq.add(new node(t.x+a[t.y+1]-a[t.y],t.y+1));
}
for(int i=1;i<=n;i++) a[i]=c[i];
// for(int i=1;i<=n;i++) System.out.print(a[i]+" ");
}
}
class node{
int x,y;
public node(int x, int y) {
this.x = x;
this.y = y;
}
}