[白俊]1186号:絶対値hip

2324 ワード
アルゴリズム#アルゴリズム# 白駿 テキストリンク

📌 質問する
割引hipは、以下の演算をサポートするデータ構造である. 
  • 配列に整数x(x≠0)を加える.
  • 配列は、終端値の最小値を出力し、配列から削除する.カットオフ値に複数の最小値がある場合、最小の数を出力し、配列から削除します.
    • プログラムは最初に空の配列から始まります.
    入力
    1行目は、演算の個数N(1≦N≦1000000)を与える.次のN行には、演算に関する情報を表す整数xが与えられる.xが0でない場合は、xを配列に追加する演算です.xが0である場合は、配列の終端値が最小の値を出力し、配列から削除します.入力された整数は-231より大きく、231より小さい.
    しゅつりょく
    入力では、0は所定の回数に等しく、答えを出力します.配列が空で、切り取り値が最小の値を出力する必要がある場合は、0を出力します.
    入力例1
    18
1
-1
0
0
0
1
1
-1
-1
2
-2
0
0
0
0
0
0
0
    サンプル出力1
    -1
1
0
-1
-1
1
1
-2
2
0
    📌 に答える
    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();

    static int N;

    static PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            int tmp1 = Math.abs(o1);
            int tmp2 = Math.abs(o2);

            if(tmp1 == tmp2)
                return o1 > o2 ? 1 : -1;
            else
                return tmp1 - tmp2;
        }
    });

    public static void base() throws IOException {
        N = Integer.parseInt(br.readLine());
    }

    public static void main(String[] args) throws IOException {
        base();

        for(int i=0; i<N; i++) {
            int now = Integer.parseInt(br.readLine());

            if(now == 0) {
               if(pq.size() == 0) {
                   sb.append("0").append("\n");
               } else {
                   sb.append(pq.poll()).append("\n");
               }
            } else {
                pq.offer(now);
            }
        }

        System.out.println(sb);
    }
}
    [アルゴリズム]階調アルゴリズム
    [BOJ]13094課題