AT_abc034_d题解
Leaves_xw
·
·
题解
思路：
二分答案加贪心。
我们设 nondu 代表二分后的浓度，那么可以得出下面这个式子：
\frac{\displaystyle\sum_{i=1}^{k}w_i\times p_i}{\displaystyle\sum_{i=1}^{k}w_i}\geq nondu
然后进行移项：
\displaystyle\sum_{i=1}^{k}w_i\times (p_i-nondu)\geq 0
随后我们设 G=w_i\times(p_i-nondu)，之后给 G 进行排序，最后贪心思想选最大的 k 个即可。