[2017 홍익대학교 프로그래밍 경진대회] 14922번 부분평균

문제

A를 길이 N인 양의 정수로 구성된 배열이라고 하자.(N>2) 정수 P, Q(0<=P<Q<N) 에 대해서 A의 부분평균 A(P, Q)를 다음과 같이 정의하자.

∑i=PQA[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

 

 

힌트

P+1<Q 라면 P<K<Q 인 정수 K가 존재하여

혹은

이다.

 

힌트를 통해 해결해야 하는 문제.

브루트포스로 풀면 조진다.

 

길이가 1인 경우는 평균이 불가능 

길이가 2라면 K + 1 < Q가 불가능 

길이가 3이라면 저 식을 만족을 못한다. 위의 식이든 아래 식이든 모순 발생.

길이가 4이상 일때 가능하게 되는데, 100이든 99든 4든 쪼개지다보면 제일 작은 평균 값을 갖는 범위인 2나 3까지 내려온다.

따라서 2나 3은 애초에 저 조건으로 구할수 없으니 그대로 구하면되고 저 4부터는 저 조건으로 구하면 되기때문에

2나 3 범위만 확인하면 된다.

 

3부터 확인해야 하는데 2범위 평균이 3범위보다 작을 것이고 인덱스를 먼저 차지하는 과정에서

틀리는 히든케이스가 있을 것이라고 판단한다.

 

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<stack>
#include<set>
#include<map>
using namespace std;
double arr[1000000];
int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	int N;
	cin >> N;
	
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	double mina = 987654321;
	int idx = 0;
	for (int i = 2; i < N; i++)
	{
		double temp = (arr[i - 2] + arr[i - 1] + arr[i]) / 3;
		if (mina > temp)
		{
			mina = temp;
			idx = i - 2;
		}
	}
	
	for (int i = 1; i < N; i++)
	{
		double temp = (arr[i - 1] + arr[i]) / 2;
		if (mina > temp)
		{
			mina = temp;
			idx = i - 1;
		}
	}

	cout << idx << endl;
	
}