AcWing 162. 黑盒子(Java对顶堆)
原题链接
中等
作者:
上杉
,
2021-05-21 12:22:51
,
所有人可见
,
阅读 396
import java.io.BufferedReader;
import java.util.PriorityQueue;
import java.util.Scanner;
/**
* @program: 算法题
* @author: 上杉
* @create: 2021-05-21 11:50
**/
public class Main {
static int M;
static int N;
static int i = 0;
static PriorityQueue<Integer> min = new PriorityQueue<>();
static PriorityQueue<Integer> max = new PriorityQueue<>((o1,o2)->o2-o1);
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
M = input.nextInt(); N = input.nextInt();
int[] put = new int[M];//元素加入的顺序
int[] get = new int[N];//get[index]代表当盒子内元素个数为get[index]时,获取++i大的数
for (int i = 0; i < M; i++) {
put[i] = input.nextInt();
}
for (int i = 0; i < N; i++) {
get[i] = input.nextInt();
}
int ui = 0;
for (int k = 0; k < M; k++) {
addNum(put[k]);
while (ui < N && get[ui] == k + 1){
i++;
max.offer(min.poll());
System.out.println(max.peek());
ui++;
}
}
}
private static void addNum(int num) {
if (min.isEmpty() && max.isEmpty()){
min.offer(num);
}else if (max.isEmpty()){
min.offer(num);
}else {
//min为空或者两个都不为空
if (num < max.peek()){
min.offer(max.poll());
max.offer(num);
}else {
min.offer(num);
}
}
}
}