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; }