二分答案

使用场景

如果答案具有单调性且有范围，那么就可以二分枚举答案，在答案合法的条件下不断逼近最优（如最大值最小或最小值最大），最后一个合法的答案就是最优解，这便是二分答案

while(l<=r){
    mid=(l+r)>>1;
    if(check(mid))
        ans=mid,r=mid-1;
   	else
        l=mid+1;
}

最后while结束后，ans便是最后一个合法的答案即最优解
另一种写法：

while(l<r){
    int mid=(l+r)>>1;
    if(check(mid))r=mid;
    else l=mid+1;
}
cout<<l<<endl;

while(r-l>eps){
    mid=(l+r)/2;
    if(check(mid))
        l=mid;
    else
        r=mid;
}

eps为精度，一般需要保留k位小数时，esp应取(10^{-(k+2)})

难度递增（本来裸的二分答案都比较简单）

欢迎转载，请注明出处：转载自：Santiego的博客