시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 437 | 124 | 96 | 35.294% |
A를 길이 N인 양의 정수로 구성된 배열이라고 하자.(N>2) 정수 P, Q(0<=P<Q<N) 에 대해서 A의 부분평균 A(P, Q)를 다음과 같이 정의하자.
\[\frac{\sum_{i=P}^{Q}{A[i]}}{Q-P+1}\]
예를 들어 주어진 배열 A의 길이가 3이고
A[0]=3, A[1]=1, A[2]=2
라고 하면 A의 가능한 모든 부분평균은 다음과 같다.
A(0,1) = (3+1)/2 = 2
A(0,2) = (3+1+2)/3=2
A(1,2) = (1+2)/2=1.5
위와 같은 경우, 모든 부분평균 중 최솟값은 A(1,2)=1.5이다. 그렇다면 주어진 조건을 만족하는 임의의 배열 A가 주어지면 A의 부분평균 중 최솟값을 가지는 것을 A(u,v) 라고 할 때, u를 출력하는 프로그램을 작성하라. (답이 여러 개일 경우 가장 작은 u의 값을 출력한다.)
N A[0], A[1], ..., A[N-1]
2 ≤ N ≤ 1,000,000, 0 ≤ A[i] ≤ 7×108
u
3 3 1 2
1
7 4 5 2 2 1 5 8
3
P+1<Q 라면 P<K<Q 인 정수 K가 존재하여
\[\frac{\sum_{i=P}^{K}{A[i]}}{K-P+1} \le \frac{\sum_{i=P}^{Q}{A[i]}}{Q-P+1} \le \frac{\sum_{i=K+1}^{Q}{A[i]}}{Q-K}\]
혹은
\[\frac{\sum_{i=K+1}^{Q}{A[i]}}{Q-K} \le \frac{\sum_{i=P}^{Q}{A[i]}}{Q-P+1} \le \frac{\sum_{i=P}^{K}{A[i]}}{K-P+1}\]
이다.