问题模型
给定 \(a,b\) 两个长度为 \(n\) 的序列，求下列式子最大值：
\[\frac{\sum_{i = 1} ^ {n} a_i · x_i}{\sum_{i = 1} ^ {n} b_i · x_i} \]其中 \(\forall i \in [1, n], x_i \in \left \{1, 0 \right \}\)。
解法
不妨设我们已经求出了这个最大值 \(k\)。
那么有：
\[\frac{\sum_{i = 1} ^ {n} a_i · x_i}{\sum_{i = 1} ^ {n} b_i · x_i} \le k \]把分母移过去：
\[\sum_{i = 1} ^ {n} a_i · x_i \le k · \sum_{i = 1} ^ {n} b_i · x_i \]再移右边：
\[\sum_{i = 1} ^ {n} a_i · x_i - k · \sum_{i = 1} ^ {n} b_i · x_i \le 0 \]\(k\) 乘进 \(\sum\) 里面：
\[\sum_{i = 1} ^ {n} a_i · x_i - \sum_{i = 1} ^ {n} k · b_i · x_i \le 0 \]合并 \(\sum\)：
\[\sum_{i = 1} ^ {n} a_i · x_i - k · b_i · x_i \le 0 \]提出 \(x_i\)：
\[\sum_{i = 1} ^ {n} x_i · (a_i - k · b_i) \le 0 \]于是一个整体贡献被我们拆成了单体贡献。
不难发现 \(k\) 影响整个式子的单调性，考虑二分 \(k\)。
此时 \(x_i\) 的取值是由 \(i\) 位置所对应的贡献决定的，把每个贡献算出来之后再去作文章。
举个例子，约束 \(\sum_{i = 1} ^ n [x_i] \le k\) 时，将贡献从大到小排序，至多取前 \(k\) 个大于 \(0\) 的贡献即可。
有时可能会与 01 背包和生成树等结合起来，具体的会在下面的例题部分细讲。