wqs二分的边界

有一个斜率不递增的凸包 假如要求的横坐标为(K) 二分的直线斜率为(mid) wqs二分取右端点 切点的右端点为(cnt)
以下代码是正确的

while(l<=r){
    int mid=l+r>>1;
    if(chk(mid))p=mid,l=mid+1;//这里!!
    else r=mid-1;
}

其中(cnt ge K)时chk返回true
为什么不能让(cnt le K)时chk返回true 然后调换r=mid-1l=mid+1?
凸包斜率不递增 (K)到左右两边斜率都等于(mid) 也就是恰好能切上
如果(cnt le K)时chk返回true 这时chk返回false 这样我们会给他判成不合法 p就不取它了 而我们是需要它的
所以这样是错的

原文地址:https://www.cnblogs.com/misaka10047/p/13255091.html