实数域上的二分——最佳牛栏

题目：

solution:

二分这个平均值，然后每个数都减去这个平均值，判断这个新序列是否有长度大于等于F的子序列的和大于0。

代码：

#include<cstdio> #include<iostream> using namespace std; double qzh[100005]; int a[100005]; int main() { int n,f; scanf("%d%d",&n,&f); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } //printf("%d %d\n",n,f); //for(int i=1;i<=n;i++) //{ // printf("%lf\n",a[i]); //} double l=0,r=2000; while(l+0.000001<=r) { double mid=(l+r)/2; for(int i=1;i<=n;i++) { qzh[i]=qzh[i-1]+a[i]-mid; } double ans=-300000000,minn=300000000; for(int i=f;i<=n;i++) { minn=min(minn,qzh[i-f]); ans=max(ans,qzh[i]-minn); } if(ans>=0)l=mid; else r=mid; } printf("%d\n",(int)(r*1000)); //printf("%d\n",(int)(l+0.5)); //int last=(int)(l*1000+0.5); //printf("%d\n",last); }