시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 299 40 33 37.931%

문제

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]

2 ≤ N ≤ 1,000,000, 0 ≤ A[i] ≤ 7×108

출력

u

예제 입력

3
3 1 2

예제 출력

1

예제 입력 2

7
4 5 2 2 1 5 8

예제 출력 2

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}\]

이다.

출처

University > 홍익대학교 > 2017 홍익대학교 컴퓨터공학과 코딩대회 E번