白駿1655の真ん中、ジャワのことを言っています.

質問する

秀彬は弟に「中間を話す」ゲームを教えている.秀彬が整数を叫ぶたびに、弟はこれまで秀彬が言った数の中で中間値を言います.前に秀斌が叫んだ数字が偶数なら、真ん中の2つの数字の中で小数を言うべきだ.
例えば、秀彬が弟に1、5、2、10、-99、7、5と順番に叫んだら、弟は1、1、2、2、2、5と順番に言うべきだ.秀彬が叫んだ数字が与えられたとき、弟が言う数字を求めるプログラムを作ってください.

入力

1行目は秀彬が叫んだ整数の個数Nを与える.Nは1以上、100000以下の自然数である.次のN行には、秀彬が叫んだ整数が順次与えられる.整数は10000以上、または10000未満です.

しゅつりょく

行ごとに1つ、N行に分けて、秀彬の弟が言う数字を順番に出力します.

に答える

問題を読んでからheapを使うことを知ったが,このように最大/最小の2つのhipを加えて中間値を探索するとは思わなかった.お尻の性格を利用するのは難しくありません(もちろん私の知らない立場では難しいですが)、お尻を使ってもタイムアウトが発生しました.なぜなら、1周あたりの印刷時間がオーバーしているからです.StringBuilderを使用して一度に出力すると解決します.
解白駿の時はアルゴリズム以外にも見逃したことをたくさん知っているようです.

import java.util.*;
public class Main{
    public static void main(String[] args){
        StringBuilder stringBuilder = new StringBuilder();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        PriorityQueue<Integer> max = new PriorityQueue<>((o1,o2)->o2-o1);
        PriorityQueue<Integer> min = new PriorityQueue<>();
        
        for(int i=0; i<n;i++){
            int N=in.nextInt();
            if((i+1)%2==0){
                min.add(N);
            }else{
                max.add(N);
            }
            if(!min.isEmpty()&&min.peek()<max.peek()){
                int tmp= min.poll();
                min.add(max.poll());
                max.add(tmp);
            }
            stringBuilder.append(max.peek()).append("\n");
        }
        System.out.println(stringBuilder);
    }
}