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

NaPF6 · 2025-07-24 21:20:49 · 算法·理论

令当前段数为 x，给定的段数为 m。

如果为下凸包：

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

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

如果为上凸包：

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

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