二分答案应用

常用trick之一。
带权二分其实是二分答案的一种间接体现。

1.最大值最小/最小值最大

明显的提示。
通过二分答案，我们可以将过程复杂的极化问题转化为判定性问题，某些时候能够大大降低思维与实现难度。

很多过程复杂的dp或图论问题都可以这样处理来简化方程或图。

例题

1.[AGC007E] Shik and Travel
二分答案转化为判定性问题，再利用状态的单调性优化决策。

2.01分数规划

形如求 \(f(x)/g(x)\) 的最大小值问题。
可以二分答案k，那么就变成了是否存在 \(f(x)-g(x)*k\leq /\geq 0\) 的判定性问题。

例题

1.最大平均边权环

3.排序/比较类问题

形如求出唯一胜者或胜出概率之类的问题。

可以二分答案x，然后将大于/小于x的人分类，记为0和1，那么可以通过数据结构维护01序列，可以由此得到比x强弱的信息。

例题

1.[HEOI2016/TJOI2016]排序