BOJ 10742

https://www.acmicpc.net/problem/10742

해답을 보고 알았지만 재밌는 이분탐색 문제이다.

 

평균이 가능한 범위는 1부터 1000000까지 이다.

이분탐색으로 답이 p이상이 가능한지 확인하면서 범위를 좁히는 형식으로 해결할 수 있다.

답이 p이상이 가능한지 안한지 확인하는 방법은..

먼저 각 요소에 p를 뺀 배열을 새롭게 만든다.

이때 만약, 길이가 $k$이상인 부분합이 $0$이상인 구간이 존재한다면 okay이다.

따라서 하나씩 $index$를 증가시키면서 미리 계산한 구간합배열 $psum$ 을 두고

$psum[index] \geq min_{i \leq index-k}(psum[i])$ 인 곳이 있는지 $min(psum[i])$를 update해주면서

확인하면 된다.

using namespace std;

int n,k;
long long arr[300000];

bool f(double x){
	double tmp[300000]={0,};
	for(int i=0;i<n;i++){
		tmp[i]=arr[i]-x;
	}
	double psum[300010]={0,};
	for(int i=1;i<=n;i++){
		psum[i]=psum[i-1]+tmp[i-1];
	}
	double m=0;
	for(int i=k;i<=n;i++){
		m=min(m,psum[i-k]);
		if(psum[i]>=m) return true;
	}
	return false;
}

int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++){
		scanf("%lld",arr+i);
	}
	double l0=1;
	double hi=1000000;
	for(int i=0;i<60;i++){
		double mid=(l0+hi)/2;
		//double 이상의 평균이 존재하는지 확인
		if(f(mid)) l0=mid;
		else hi=mid;
	}
	printf("%.6f",l0);
	return 0;
}