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),也就是这个(K)尴尬地处于一个平台上
正确的代码应该返回(cnt ge K)时的最大的斜率,容易发现这时应该是切到平台上的,我们得到了正确的答案。
如果返回(cnt le K)时的最小的斜率,可以发现这时显然并没有切到平台上(切到平台上的话由于取右端点肯定是会(ge K)的)。
所以这样是错的。

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