알고스팟 문제 링크: https://algospot.com/judge/problem/read/RUNNINGMEDIAN
algospot.com :: RUNNINGMEDIAN
변화하는 중간값 문제 정보 문제 한 수열의 중간값(median)은 이 수열을 정렬했을 때 가운데 오는 값입니다. 예를 들어 {3,1,5,4,2}를 정렬했을 때 가운데 오는 값은 3이지요. 수열의 길이가 짝수일 때
algospot.com
수열을 다음과 같은 방법으로 추가한다고 하자.
A[0] = 1983
A[ i ] = (A[ i-1 ] * a + b) % 20090711
한 수열의 중간값은 수열에 새로운 수가 추가될 때마다 바뀔 수 있다.
수열에 새로운 수가 추가될 때마다 해당 수열의 중간값의 다 더한 중간값의 합을 20090711로 나눈 나머지를 구하는 문제이다.
수열을 추가해 나갈때 다음과 같은 불변식을 지키며 최대, 최소 힙을 유지한다면 최대 힙의 top값이 현재 수열의 중간값이 된다.
1. 최대힙의 크기는 최소힙의 크기와 같거나 1 더 크다.
2. 최대힙의 top값 <= 최소힙의 top값
코드 원본: https://github.com/sbl133/JongmanBook/blob/main/23.%20priorityQueue%20and%20Heap/RUNNINGMEDIAN.cpp
GitHub - sbl133/JongmanBook
Contribute to sbl133/JongmanBook development by creating an account on GitHub.
github.com
댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!
reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2
'Algorithm > algospot' 카테고리의 다른 글
| algospot 족보 탐험 (문제 ID: FAMILYTREE) c++ (0) | 2021.10.14 |
|---|---|
| algospot 등산로 (문제 ID: MORDOR) c++ (0) | 2021.10.14 |
| algospot 삽입 정렬 뒤집기 (문제 ID: INSERTION) c++ (0) | 2021.10.09 |
| algospot 너드인가, 너드가 아닌가? 2 (문제 ID: NERD2) c++ (0) | 2021.10.07 |
| algospot 요새 (문제 ID: FORTRESS) c++ (0) | 2021.10.06 |