//上面的为小根堆
PriorityQueue<Integer> up = new PriorityQueue<Integer>();
//下面的为大根堆
PriorityQueue<Integer> down = new PriorityQueue<Integer>((x, y) -> y - x);
来一个数的时候优先给up
up小根堆永远比down多一个数,动态维持
当up比down多超过一个的时候才会poll一个给down
输入个数为奇数的时候输出的中位数为up.peek()
为偶数时输出的为两个堆顶的平均值
blablabla
JAVA代码:
import java.util.PriorityQueue;
import java.util.Scanner;
public class AC106RunningMedian {
//上面的为小根堆
PriorityQueue<Integer> up = new PriorityQueue<Integer>();
//下面的为大根堆
PriorityQueue<Integer> down = new PriorityQueue<Integer>((x, y) -> y - x);
/** initialize your data structure here. */
public void addNum(int num) {
//大于等于大顶堆顶的放上面
if(down.isEmpty() || num>=down.peek())
up.add(num);
//小于大顶堆顶则放下面
else {
down.add(num);
up.add(down.poll());
}
if(up.size()>down.size()+1) {
down.add(up.poll());
}
}
public double findMedian() {
if(up.size()==down.size() + 1)
return up.peek();
else
return (down.peek()+up.peek())/2;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
AC106RunningMedian c=new AC106RunningMedian();
Scanner scan = new Scanner(System.in);
int M = scan.nextInt();
for(int i=1; i<=M; i++) {
int n1= scan.nextInt();
int number= scan.nextInt();
System.out.println(n1+" "+(number+1)/2+" ");
for(int j=1; j<=number; j++) {
int a= scan.nextInt();
c.addNum(a);
if(j%20==0) {
System.out.println();
}
if(j%2==1) {
System.out.print(c.findMedian()+" ");
c.findMedian();
}
}
System.out.println();
c.up.clear();
c.down.clear();
}
}
}