6개의 댓글이 있습니다.
-
-
장홍준 -
첫 번째 문제는 각 원소를 (i, i번째 원소까지의 누적합)으로 n개의 점을 만들어 컨벡스헐을 활용하면, 컨벡스헐을 구하는데 O(N log N)이 걸리는 걸 제외하면 O(N)에 풀 수 있습니다.
(올해 코더스하이 예비소집 문제와 거의 유사한 것 같아 링크 남겨드립니다. https://www.acmicpc.net/problem/10213)두 번째 문제는 정렬하는 시간을 제외하면 O(N)에 풀리는데, 결국 정렬의 시간복잡도가 O(N)일 수 있냐는 것인데 이는 불가능합니다.
9년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
mujugi
안녕하세요
혼자 고민해보다가 도저히 모르겠어서
질문드립니다.
어떤 배열 a 가 있고 배열 안에는 임의의 정수 n개가 들어있습니다
이 배열의 합의 최대 평균 구간인 L1 ~ L2를 찾는 문제입니다
O(n)에 가능하다고 하는데 도저히 방법을 모르겠습니다.
(사실 배열의 모양이 어떤 모양인지도 모르겠습니다)
원문입니다
Given a sequence of N 64-bit integers, find a sequence of at least L consecutive integers that has the highest average. O(N^2) not too hard; O(N) possible but much harder. O(NL) follows since there must exist an optimal interval between L and 2L. Hint: can compute average from i to j in O(1) time with O(N) preprocessing by precomputing prefix[i] = a[0] + ... + a[i] for each i. Then the average of the interval from i to j is (prefix[j] - prefix[i]) / (j - i + 1).
(1,3),(2, 4),(6,8),(5.5,9)
이런 구간 배열이 있을때 union된 최대 거라는
(1,4), (5.5,9) 즉 3 + 3.5 = 6.5 가 될텐데요
소수점이 없다고 가정하면 O(n)안에 계산을 할 수 있는데
소수점이 있을때도 worst O(n)으로 계산 할 수 있을까요?
일반적으론 정렬해서 O(n log n) 으로 풀린다고 합니다
감사합니다
11년 전