适用情况:题目限定要刚好选择 \(m\) 个东西时,某个价值的最大/最小。并且可以很容易思考出一个没有 \(m\) 限制的做法,这个时候就要警惕的思考可不可以WQS二分
如果是dp,起初可以设计出一个有 \(m\) 限制的做法,但是状态已经是 \(O(n^2)\) 了。如果此时发现没有题目的 \(m\) 限制,可以设计出 \(O(n)\) 的dp,那么就也可以用WQS二分。
上面这两条是很重要的。
一种方便的理解方式是:理解为给一个惩罚,通过不断调整惩罚使得最后的答案刚刚好选择上了 \(m\) 个东西,满足题目的限制。
比如 Tree I 这个题,我们可以给每一条白边的边权加上惩罚,然后二分惩罚,直到有一次这个惩罚使得恰好选出need条白边,当然有可能不会恰好need条但是结束,不要慌这种情况是共线的情况,我们照样当做是need条算就可以了,之间的误差会自动中和掉。
