题目描述
农夫约翰的农场由 N 块田地组成,每块地里都有一定数量的牛,其数量不会少于1头,也不会超过2000头。
约翰希望用围栏将一部分连续的田地围起来,并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区域内至少需要包含 F 块地,其中 F 会在输入中给出。
在给定条件下,计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。
算法:二分+前缀和+双指针
时间复杂度:$O(log(n)+2·n)$
(1)一部分的最值问题是可以使用二分进行求解的
(2)求某个前缀的最小值可以使用双指针算法优化掉一重循环
C++代码
#include<iostream>
using namespace std;
const int N=100010;
double w[N],a[N];
int n,k;
bool judge(double avg)
{
//维护前缀与均值的大小
for(int i=1;i<=n;i++)a[i]=a[i-1]+w[i]-avg;
double mins=0;
for(int i=k;i<=n;i++){
mins=min(mins,a[i-k]);
//在i处之前的k个位置的最小值
if(a[i]-mins>=0)return true;
}
return false;
}
int main()
{
cin>>n>>k;
double l=0,r=0;
for(int i=1;i<=n;i++){
scanf("%lf",&w[i]);
r=max(r,w[i]);
}
while(r-l>1e-5){
double mid=(r+l)/2;
if(judge(mid))l=mid;
else r=mid;
}
printf("%d\n",(int)(1000*r));
return 0;
}