Best Cow Fences(前缀和+特殊二分)

之前的二分大多数都是整数类型的,今天又学到一种新型的二分,浮点数的二分,浮点数的二分可太巧妙了.且听我细细分说:
:OpenJudge - 2018:Best Cow Fences

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k;
double a[N],s[N],l,r;
bool check(double u)
{
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]-u;
    double minn=0;
    for(int i=0,j=k;j<=n;j++,i++){
        minn=min(minn,s[i]);
        if(s[j]>minn) return true; 
    }
    return false;
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    l=0,r=3000;
    while(r-l>1e-8){
        double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    cout<<int(r*1000);
    return 0;
}

这里有很多注意点,在浮点数二分的时候,不能执行r-1,l+1的操作,万一答案在l到l+1之间呢?这个是一个注意点

题目有说到向下取整，将最后改成cout<<int(left*1000) 是不对的，那为什么会这样？

举个例子，比如答案为6.9876543……,在精度控制在1e-5的情况下，假设得到的区间为(6.987652,6.987655),这里输出的都是6987没有问题；但是如果答案本身比1e-3精度小呢?比如答案为6.78，那么得到的区间就会为(6.77999,6.78001),用left输出就错了。

所以说，当答案的精度比1e-3更小时，你的左边区间只能将我小数点后最后一位减1，后面补上9，用左边的区间就会出错。而右边的区间会在1e-3位后面补上很小很小的数，但是我们用int转化，把这些都舍掉，正好可以得到正确答案。当然，答案的精度比1e-3更大时，就左右都可以，与向下取整契合。