set 같은 것을 이용한 다해두 결국 pointer 접근에 linear가 되고..

매번 sort할 경우에도 시간초과고..

예전에 실패했던것들 보고 있는데 피자는 성공했는데

이 문제는 며칠 고민해봐도 감이 안오네요..

yukariko   1년 전

저는 sqrt decomposition 으로 풀었습니다..

하지만 더 간단명료한 방법이 있죠

중앙값을 기준으로 더 작은 값들을 모아둔것과, 더 큰값을 모아둔 집합을 나눠서 관리하고

숫자가 추가될 때마다 중앙값과 집합을 갱신해주는 방법입니다.

구현은 직접 해보시길..

아이디어 접근 방향이 생각 안났었는데 구현은 일단 직접 해보겠습니다 감사합니다!!

맞았습니다 떴습니다!!

나눠서 관리하는걸 생각을 못해가지고 고민을 하고 있었네요 ㅋㅋㅋㅋㅋㅋㅋㅋ

mendou12   1년 전

비슷한 문제가 알고스팟에도 있어용

한번 풀어보시는 것도 좋을 거 같아요

http://algospot.com/judge/problem/read/RUNNINGMEDIAN

댓글을 작성하려면 로그인해야 합니다.