白駿1655中間

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

白駿1655中間

実施前の考え方


ArrayListを使用して入力し、リスト内の配列の長さ/2-1で中間値を検索します.

残念な点


入力を続行して配列をソートするには時間がかかるため、タイムアウトします.
=>優先キューソリューションの使用
ただし、maxheap、minheapを使用して中間値を検索する方法は考えられませんので、優先キューを使用して中間値を検索する方法を参照してください.
まず、maxheapとminheapを使います
maxheapの場合、配列の値は0～midです.
minheapの場合、配列の場合、maxheapの最大値を出力するたびに中間値を検索するmidとendの間の値があります.

コード#コード#

package argorithm_study_june;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class backjoon_1655_가운데를말해요 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		PriorityQueue<Integer> maxheap = new PriorityQueue<Integer>((o1,o2)->o2-o1);
		PriorityQueue<Integer> minheap = new PriorityQueue<Integer>((o1,o2)->o1-o2);
		
		for (int i = 0; i < N; i++) {
			int num = Integer.parseInt(br.readLine());
			
			if(maxheap.size()==minheap.size()) 
				maxheap.add(num);
			else
				minheap.add(num);
			if(!maxheap.isEmpty()&&!minheap.isEmpty()) {
				if(maxheap.peek()>minheap.peek()) {
					int temp = minheap.poll();
					minheap.add(maxheap.poll());
					maxheap.add(temp);
				}
			}
			sb.append(maxheap.peek() + "\n");
			
		}
		System.out.println(sb);
	}
}
MaxNonoverlappingSegments
spring day5