PKU 2018-Best Cow Fences

問題概要

全て長さがF以上の区間について、平均値が最大のものを求めよ。

解法

最大平均値がx以上であるかは部分和と区間最大値を考えることでO(N)で求めることが出来る。
xについて二分探索を行なう

実装(C++)

#include <cstdio>
#include <iostream>
using namespace std;
int N,F;
typedef long long lli;
lli INF=1LL<<60;
int a[100000];
lli sum[100001];
lli rmq[211111];
bool solve(int x){
	sum[0]=0;
	for(int i=0;i<N;i++){
		sum[i+1]=sum[i]+a[i]-x;
	}
	fill(rmq,rmq+211111,-INF);
	rmq[N]=sum[N];

	for(int i=N-1;i>=0;i--){
		rmq[i]=max(rmq[i+1],sum[i]);
	}
	for(int i=0;i<N;i++){
		if(rmq[i+F]-sum[i]>=0)return true;
	}
	return false;
}
int main() {
	scanf("%d%d",&N,&F);
	for(int i=0;i<N;i++){
		scanf("%d",a+i);
		a[i]*=1000;
	}
	int low=0,high=2000*1000+100;
	while(low+1<high){
		int mid=(low+high)/2;
		if(solve(mid)){
			low=mid;
		}else{
			high=mid;
		}
	}
	printf("%d\n",low);
	return 0;
}