令 \(p^{'}_i=\frac{p_i}{100w_i}\)。
题意即最大化 \(\dfrac{\sum\limits_{i=1}^kp^{'}_{\texttt{number}_i}}{\sum\limits_{i=1}^kw_{\texttt{number}_i}}\)。
这就是一个很典的 \(01\) 分数规划了。
时间复杂度 \(O(Tn\log n)\)，\(T\) 为二分次数。
ABC034D 食塩水
发布时间 2023-05-08 10:07:15作者: CJzdc
令 \(p^{'}_i=\frac{p_i}{100w_i}\)。
题意即最大化 \(\dfrac{\sum\limits_{i=1}^kp^{'}_{\texttt{number}_i}}{\sum\limits_{i=1}^kw_{\texttt{number}_i}}\)。
这就是一个很典的 \(01\) 分数规划了。
时间复杂度 \(O(Tn\log n)\)，\(T\) 为二分次数。