二分平均数,判断在该平均数下是否有一个区间长度至少为f的区间满足题意。
#include<bits/stdc++.h>
using namespace std;
const int nn=100010;
int n,f;
double a[nn],b[nn],sum[nn];
double e,l,r,mid;
inline bool check(double x)
{
for(int i=1;i<=n;++i)
b[i]=a[i]-mid,sum[i]=sum[i-1]+b[i];
double minn=1e7;
for(int i=f;i<=n;++i)
{
minn=min(minn,sum[i-f]);
if(sum[i]-minn>0) return true;/*问题1:在统计sum的时候是不需要让他大于mid的,而是需要大于0*/
}
return false;
}
int main()
{
scanf("%d%d",&n,&f);
for(int i=1;i<=n;++i)
scanf("%lf",&a[i]);
e=1e-5;
l=-1e5,r=1e7;
while(r-l>e)
{
mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
cout<<int(r*1000)<<endl;//问题2:注意是(r*1000)要转化成int输出
return 0;
}