一般形式

给出 wi∈{0,1}w_i\in\{0,1\}，最小化或最大化

∑i=1nai×wi∑i=1nbi×wi\displaystyle\frac{\sum\limits_{i=1}^na_i\times w_i}{\sum\limits_{i=1}^nb_i\times w_i}

求解方法

我们用二分来求解

∑ai×wi∑bi×wi≥mid⟹∑ai×wi−mid×∑bi⋅wi≥0⟹∑wi×(ai−mid×bi)≥0\displaystyle \begin{aligned} &\frac{\sum a_i\times w_i}{\sum b_i\times w_i}\ge mid\\ \Longrightarrow&\sum a_i\times w_i-mid\times \sum b_i\cdot w_i\ge 0\\ \Longrightarrow&\sum w_i\times(a_i-mid\times b_i)\ge 0 \end{aligned}

变式

ln⁡Ans=1c∑i=1cln⁡wi\ln\mathrm{Ans}=\frac{1}{c}\sum_{i=1}^{c}\ln w_i

为了去掉 1c\frac{1}{c}，可以变成 0/1 分数规划问题。我们需要让这个大于 00。

∑i=1c(ln⁡vi−mid)\sum_{i=1}^c \left(\ln v_i-mid\right)

其实这个变式我们可以把分母的所有的 bb 都看成 11。

P3705 [SDOI2017] 新生舞会。