白準2696中央値(Java、Java)を求めます

17683 ワード
アルゴリズム#アルゴリズム# テキストリンク
今回解決した問題.
白駿2696号は中央値を求めます.

📕 提问链接


❗¥コード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static List<Integer> map;
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> minQ;
        PriorityQueue<Integer> maxQ;
        StringBuilder sb = new StringBuilder();
        while(T-- > 0)
        {
            map = new ArrayList<>();
            int N = Integer.parseInt(br.readLine());
            sb.append((N+1)/2).append("\n");
            // N이 10 이상
            while(N > 9)
            {
                st = new StringTokenizer(br.readLine());
                getList(10);
                N -= 10;
            }
            // 나머지 or 10 미만
            if(N > 0)
            {
                st = new StringTokenizer(br.readLine());
                getList(N);
            }
            minQ = new PriorityQueue<>(Collections.reverseOrder());
            maxQ = new PriorityQueue<>();

            int flag = 1;
            for(int next : map)
            {
                if(minQ.size() == maxQ.size()) minQ.add(next);
                else maxQ.add(next);
                if(!maxQ.isEmpty())
                {
                    int left = minQ.peek();
                    int right = maxQ.peek();
                    if(left > right)
                    {
                        maxQ.add(minQ.poll());
                        minQ.add(maxQ.poll());
                    }
                }
                if((flag % 2) > 0) sb.append(minQ.peek()).append(" ");

                flag++;
                // 10개 찍었으면 줄바꿈
                if(flag > 19)
                {
                    sb.append("\n");
                    flag = 0;
                }
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }
    static void getList(int n)
    {
        for(int i = 0; i < n; i++)
        {
            map.add(Integer.parseInt(st.nextToken()));
        }
    }
}

📝 に答える


n個の大きさの数列を入力すると、これまで入力したローカル数列の中心値が奇数順に出力されるという問題がある.
2つのキューを作成できます.1つのキューの優先度は最高値と最高値であり、常にpeek値を中間値に維持します.最安値優先のMINQのpeekを中間価格にしました
minqは常に中間値より小さい値を含み、maxqは常に中間値より大きい値を有する.したがって、minqのpeek値は、最初の奇数入力が完了すると常に中間値とすることができる.
2つのキューのサイズは同じ時点、すなわち最初の奇数入力ではminqで中間値がpeekに存在する必要があるため、サイズを比較することで、どのキューに値を含めるかを決定できます.この問題は、中間値のリフレッシュを継続し、flag値が奇数の場合にsbに出力値を積算することで解決します.

📜 ポスト


長い間ですが、以前似たような問題をしたことがあることを思えば、解決は難しくありません.もしかすると~まだ足りなければ、次の質問にも答えられるかもしれません!
https://www.acmicpc.net/problem/1655
データ構造の実践——一般化表の原子統計
ｶﾀｶﾀｶﾀｯﾀｰﾝのほかにクリック音とカーソルの移動音も可視化した！