模型

• 求解一组 $x$ 最大化下式：

$$\begin{aligned} \frac{{\sum_{i=1}^n {a_{i}*x_{i}}}}{\sum_{{i=1}}^n {b_{i}*x_{i}}} \end{aligned} $$

• 二分答案，转化为判定下式：

$$\begin{aligned} \frac{{\sum_{i=1}^n {a_{i}*x_{i}}}}{\sum_{{i=1}}^n {b_{i}*x_{i}}}\geq mid \end{aligned} $$

• 化一下得到：

$$\begin{aligned} \ {\sum_{i=1}^n {a_{i}*x_{i}}}\geq{\sum_{i=1}^n {b_{i}*x_{i}}}\times mid \\ \sum_{i=1}^n {x_{i}\times(a_{i}-b_{i}\times mid) \geq mid} \end{aligned}$$

• 这样就可以 $O(n)$ 判定了