hanwjdgh   7년 전

K의 개수만큼 임시배열에 소팅을해서 넣고 그안에서 해당하는 중앙값을 구해

더했는데 예제는 답이 나오지만 틀렸다고 나옵니다

이유좀 알려 주세요

아니면 반례같은 거라도

etaehyun4   7년 전

1. 마지막 답의 범위가 어떻게 될지 생각해보세요

2. 고치셔도 시간초과가 발생할 것 같은 추측을 해 봅니다..

hanwjdgh   7년 전

마지막 답의 범위라는게 

N = 250,000 /  K=5,000 일때는 말씀하시는 건가요?

etaehyun4   7년 전

아니요, 출력하는 값의 범위를 생각해보시라는 뜻이었습니다 (최악의 경우)

hanwjdgh   7년 전

예시좀 들어주실수 있으신가요 부탁드립니다

etaehyun4   7년 전

모든 온도가 65535이고 N=250000, K = 1 인 경우 답이 뭘까요

hanwjdgh   7년 전

65536*250000 이라 int 를 벗어나서

sum을 long long으로 바꿔야 하지않나요? 

etaehyun4   7년 전

long long 은 %lld 를 씁니다. 그리고 시간초과가 발생할텐데, 시간복잡도가 O(N K log K) 이기 때문입니다.

hanwjdgh   7년 전

그러면 어떤식으로 해야할까요?

etaehyun4   7년 전

이 문제는 그냥 풀어서는 안되고 BIT 나 STL 자료구조들을 써야 해결 가능한 문제입니다 (다른 Solution 도 있을 수 있고요)


혹시 더 궁금하시면 이 문제 관련 질문들을 찾아보거나 해당 내용을 공부해보시면 될 것 같습니다

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