6065 : K번째 최솟값 유지
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
K번째 최솟값 유지
크기 K인 최대힙(Max-Heap)을 유지하여, 실시간으로 숫자가 입력될 때마다 지금까지 입력된 수들 중 K번째로 작은 수를 $O(\log K)$에 출력하시오.
알고리즘 힌트:
1. 크기 K의 최대힙을 유지합니다.
2. 새 수가 들어오면, 힙 크기가 K 미만이면 그냥 삽입합니다.
3. 힙이 K개 차면, 새 수가 힙 최댓값(=현재 K번째 최솟값)보다 작을 때만 교체합니다.
4. 힙의 루트(최댓값)가 현재 K번째 최솟값입니다.
[제약 조건]
• 쿼리 수 $N$: $1 \le N \le 100{,}000$ (정수)
• $K$: $1 \le K \le$ 현재 원소 수
• 각 원소: $1 \le x \le 10^9$ (정수)
크기 K인 최대힙(Max-Heap)을 유지하여, 실시간으로 숫자가 입력될 때마다 지금까지 입력된 수들 중 K번째로 작은 수를 $O(\log K)$에 출력하시오.
알고리즘 힌트:
1. 크기 K의 최대힙을 유지합니다.
2. 새 수가 들어오면, 힙 크기가 K 미만이면 그냥 삽입합니다.
3. 힙이 K개 차면, 새 수가 힙 최댓값(=현재 K번째 최솟값)보다 작을 때만 교체합니다.
4. 힙의 루트(최댓값)가 현재 K번째 최솟값입니다.
[제약 조건]
• 쿼리 수 $N$: $1 \le N \le 100{,}000$ (정수)
• $K$: $1 \le K \le$ 현재 원소 수
• 각 원소: $1 \le x \le 10^9$ (정수)
입력 설명
첫째 줄에 정수의 개수 N과 기준 K가 주어집니다. (1 ≤ K ≤ N ≤ 50,000)
둘째 줄에 N개의 정수가 공백을 사이에 두고 주어집니다.
둘째 줄에 N개의 정수가 공백을 사이에 두고 주어집니다.
출력 설명
매 숫자가 입력될 때마다, 지금까지 입력된 수들 중 K번째로 작은 수를 출력합니다.
입력된 수의 개수가 K개 미만이면 -1을 출력합니다.
입력된 수의 개수가 K개 미만이면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3
3 1 4 1 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
-1
-1
3
3
4