# [Gold IV] 부분평균 [문제 링크](https://www.acmicpc.net/problem/14922) ## 문제 설명 <p>A를 길이 N인 양의 정수로 구성된 배열이라고 하자.(N>2) 정수 P, Q(0<=P<Q<N) 에 대해서 A의 부분평균 A(P, Q)를 다음과 같이 정의하자.</p> <p>\(\frac{\sum_{i=P}^{Q} A[i]}{Q-P+1}\)</p> <p>예를 들어 주어진 배열 A의 길이가 3이고</p> <p>A[0]=3, A[1]=1, A[2]=2</p> <p>라고 하면 A의 가능한 모든 부분평균은 다음과 같다.</p> <p>A(0,1) = (3+1)/2 = 2</p> <p>A(0,2) = (3+1+2)/3=2</p> <p>A(1,2) = (1+2)/2=1.5</p> <p>위와 같은 경우, 모든 부분평균 중 최솟값은 A(1,2)=1.5이다. 그렇다면 주어진 조건을 만족하는 임의의 배열 A가 주어지면 A의 부분평균 중 최솟값을 가지는 것을 A(u,v) 라고 할 때, u를 출력하는 프로그램을 작성하라. (답이 여러 개일 경우 가장 작은 u의 값을 출력한다.)</p> ## 입력 <pre>N A[0], A[1], ..., A[N-1]</pre> <p>2 ≤ N ≤ 1,000,000, 0 ≤ A[i] ≤ 7×10⁸</p> ## 출력 <pre>u</pre> ## 힌트 <p>P+1&lt;Q 라면 P&lt;K&lt;Q 인 정수 K가 존재하여</p> <p>\(\frac{\sum_{i=P}^{K} A[i]}{K-P+1} \leq \frac{\sum_{i=P}^{Q} A[i]}{Q-P+1} \leq \frac{\sum_{i=K+1}^{Q} A[i]}{Q-K}\)</p> <p>혹은</p> <p>\(\frac{\sum_{i=K+1}^{Q} A[i]}{Q-K} \leq \frac{\sum_{i=P}^{Q} A[i]}{Q-P+1} \leq \frac{\sum_{i=P}^{K} A[i]}{K-P+1}\)</p> <p>이다.</p> ## 풀이 인접한 2개, 3개의 값의 최소 평균만 비교하면 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; ll a[1'000'000]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=0;i<n;i++) cin >> a[i]; ll idx=0, sum=INT_MAX, size=1; for(int i=0;i<n-1;i++) { if((a[i]+a[i+1])*size<sum*2) { idx=i; size=2; sum=a[i]+a[i+1]; } if(i+2<n && (a[i]+a[i+1]+a[i+2])*size<sum*3) { idx=i; size=3; sum=a[i]+a[i+1]+a[i+2]; } } cout << idx; } ```