poj 2018 Best Cow Fences 二分查找dp_best cow fences题解

 惭愧 参考bloghttp://www.cppblog.com/varg-vikernes/archive/2010/03/02/108737.aspx

 #include<iostream>
 using namespace std;
 #define doit(n) for(int i=1;i<=n;i++)
 double a[100005],sum[100005];
 int n,m;
 double r,l;
 bool chack(double val)
 {
        double temp;
        double pre=(sum[m-1])-(m-1)*val;//这里默认其实位置为1 
        for(int i=m;i<=n;i++)
        {
            temp=(sum[i]-sum[i-m])-m*val; // 计算长度为m的和 
            pre+=(a[i]-val); //一段一段的往上加 
            pre=max(temp,pre); //这里用来更新起始位置 
            if(pre>-1e-6) //注意这里为负值 0的时候也想左翼 
            return 1;
        }
        return 0;
}
 int main()
 {
        
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            r=0;l=0x7FFFFFFF;
            memset(sum,0,sizeof(sum));
            doit(n)
            {
                scanf("%lf",&a[i]);
                sum[i]=sum[i-1]+a[i];
                l=min(a[i],l);
                r=max(a[i],r);
            }
            while(r-l>1e-6)
            {
                double mid=(r+l)/2;
                if(chack(mid))
                {
                    l=mid;
                }
                else
                r=mid;
            }
            printf("%d\n",(int)(r*1000)); //这里选值必须选右面，要是选左面强制转换的时候会少一也就是说有可能6499 
        }
        return 0;
}