二分答案

一句话理解

二分答案：对答案值域二分，用 check 判断这个答案够不够。

为什么要学

CSP-S / NOIP 高频思想。

讲解

不是在下标上二分，而是在“可能的答案”上二分。check 为真就尝试更优的一侧。

先暴力枚举答案，确认单调，再改二分。

例子

最少需要多少天完成。mid 天能完成则尝试更少，否则增加天数。

常见错误

• check 复杂度太高，log 乘上去仍 TLE。
• 值域用 int 却答案超 int。