本题 二分法 要点注意
查看原帖
本题 二分法 要点注意
1543702
dsfg111楼主2024/11/11 08:56

本题直接套二分法的模板很可能出问题。个人得到的一个可行的写法是 (此处仅展示关健的区间控制)

mid=(l+r+1)/2

结果大于等于K:l=mid

结果小于K:r=mid-1

此处不能写l=mid+1,因为mid可能为最终结果 需要保留。

而r就无所谓了,通过-1防止死循环

此处也不能写mid=(l+r)/2,会死循环。举个例子:

l=1,r=2

mid=1

结果大于等于K:l=1

这就死循环了,但如果是mid=(l+r+1)/2,mid会更偏向r

此时mid=2

结果大于等于K:l=2

结果大于等于K:r=1

这样两种情况都能通过,并且保留了大于等于K的mid

2024/11/11 08:56
加载中...