题意

给定 \(a_1,a_2,\cdots a_n\) 以及 \(b_1,b_2,\cdots b_n\)，要求最大化： \[ \frac{\sum_{i = 1}^n a_ix_i}{\sum_{i = 1}^n b_ix_i} \] 其中 \(\forall 1\le i \le n, x_i \in \{0, 1\}\)。

解法

我们可以二分答案 \(L​\)，这样这个问题就转变为：能否求出一组解 \(x​\)，使得 \(\frac{\sum_{i = 1}^n a_ix_i}{\sum_{i = 1}^n b_ix_i} \ge L​\)？

对不等式进行变形： \[ \begin{aligned} \frac{\sum_{i = 1}^n a_ix_i}{\sum_{i = 1}^n b_ix_i} &\ge L \\ \sum_{i = 1}^n a_ix_i &\ge L\sum_{i = 1}^n b_ix_i \\ \sum_{i = 1}^n a_ix_i - L\sum_{i = 1}^n b_ix_i &\ge 0 \\ \sum_{i = 1}^n (a_i - Lb_i)x_i &\ge 0 \end{aligned} \] 我们计算 \(\sum_{i = 1}^n (a_i - Lb_i)x_i\) 的最大值，即构造 \(x\) 使 \(x_i = 1\) 当且仅当 \(a_i - Lb_i > 0\)，并判断最大值的正负性，在此基础上不断二分答案即可。时间复杂度为 \(O(n\log L_{max})\)。