【实数域上的二分，二分答案】POJ 2018 Best Cow Fences

链接

http://poj.org/problem?id=2018

大意

给定一些序列，求出长度至少为m$m$的子序列的平均值最大

思路

因为奶牛的数量不可能为负数，所以该数据具有单调性，考虑二分

代码

#include<cstdio>
#include<algorithm>
#define eps (1e-5)
#define re register
#define r(i,a,b) for(re int i=a;i<=b;i++)
using namespace std;int n,m;
double a[100001],s[100001],l=-1e6,r=1e6;
inline bool check()//判断其平均值是否满足要求
{
    double minn=1e9;
    r(i,m,n) {minn=min(minn,s[i-m]);if(s[i]-minn>=0) return true;}//我们使左端点尽量小，右端点与左端点的差若能超过0说明满足要求
    return false;
}
signed main()
{
    scanf("%d%d",&n,&m);
    r(i,1,n) scanf("%lf",a+i);
    while(r-l>eps)
    {
        double mid=(l+r)/2;
        r(i,1,n) s[i]=s[~-i]+a[i]-mid;
        if(check()) l=mid;else r=mid;
    }
    printf("%d",(int)(r*1000));//输出
}