AcWing 146. 序列 超级详细注释版(Java优先队列)
原题链接
简单
作者:
雪豹不讲武德
,
2024-03-11 11:35:29
,
所有人可见
,
阅读 19
import java.util.*;
import java.io.*;
public class Main {
static int N = 2010;
static int[] a = new int[N]; // 排序数组 后期将被重复使用 接收第一个数组
static int[] b = new int[N]; // 轮询数组 接收剩下的n-1个数组
static int[] c = new int[N]; // 临时数组 用于存储前m大的数
static int n, m;
public static void merge() { // 数组均为全局变量 返回值为void即可
// 建立优先队列
// 优先队列中存放自定义的类PII,需要手写排序重载
PriorityQueue<PII> heap = new PriorityQueue<PII>(new Comparator<PII>() {
@Override
public int compare(PII o1, PII o2) { // 小根堆 且以第一个元素进行排序
return o1.sum - o2.sum;
}
});
for(int i = 0; i < m; ++i) heap.add(new PII(a[0] + b[i], 0)); // 读入矩阵的第一列
for(int i = 0; i < m; ++i) {
PII t = heap.poll();
c[i] = t.sum; // 存入暂存数组中
int v = t.sum; // 用于后期推导
int p = t.idx; // 获取当前的选中数组的下表
heap.add(new PII(v-a[p]+a[p+1], p+1)); // 更新堆的状态
}
for(int i = 0; i < m; ++i) a[i] = c[i]; // 转储
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
while(T -- > 0) {
String[] s1 = br.readLine().split(" ");
// 设 n行m列 矩阵
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
String[] s2 = br.readLine().split(" ");
// 获取第一个数组
for(int i = 0; i < m; ++i) a[i] = Integer.parseInt(s2[i]);
Arrays.sort(a, 0, m); // 对a数组进行排序
for(int i = 0; i < n - 1; ++i) { // 剩下n-1个序列依次读入数组中
String[] s3 = br.readLine().split(" ");
for(int j = 0; j < m; ++j) // 快速读入数据
b[j] = Integer.parseInt(s3[j]);
merge(); // a与b进行比较获取前n大个数据存储于a中
}
for(int i = 0; i < m; ++ i) {
System.out.printf("%d ", a[i]);
}
System.out.println();
}
}
}
class PII {
int sum, idx;
public PII(int sum, int idx) {
this.sum = sum;
this.idx = idx; // 存放a数组的下标
}
}