专栏文章

关于 WQS 二分的一些细节问题

2025/07/24 21:20算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论: 0 条
当前快照: 1 份
快照标识符: @mior4n02
此快照首次捕获于: 2025/12/02 23:47
此快照最后确认于: 2025/12/02 23:47

令当前段数为

x

，给定的段数为

m

。

如果为下凸包：

当段数尽量取最大时，那么当 $x<m$ 时 $l\gets mid+1$ ；当 $x>m$ 时 $r\gets mid$ 。

$mid=\left\lfloor\frac{l+r}{2}\right\rfloor$ 。
当段数尽量取最小值时，那么当 $x<m$ 时 $l\gets mid$ ；当 $x>m$ 时 $r\gets mid-1$ 。

$mid=\left\lfloor\frac{l+r+1}{2}\right\rfloor$ 。

如果为上凸包：

当段数尽量取最大时，那么当 $x<m$ 时 $r\gets mid-1$ ；当 $x>m$ 时 $l\gets mid$ 。

$mid=\left\lfloor\frac{l+r+1}{2}\right\rfloor$ 。
当段数尽量取最小时，那么当 $x<m$ 时 $r\gets mid$ ；当 $x>m$ 时 $l\gets mid+1$ 。

$mid=\left\lfloor\frac{l+r}{2}\right\rfloor$ 。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...