ABC034 ~食塩水~ - banbooooのブログ

D - 食塩水
解いたのでメモ。悩んだけど、どうやら典型の模様。
蟻本p132の「平均最大化」とほとんど同じ問題。
最初は、ナップザック問題っぽいなぁと思って、DPを必死に考えてたけど
よくよく考えてみれば以下の式は別物。
本問 : $max(\dfrac{\sum v}{\sum w})$
ナップザック : $max(\sum v) \ \ {\sum w \leq const}$

~ アルゴリズム ~
目標の $p$ を決めてあげて、この濃度以上のものが作れるか判定する。
濃度 $p$ 以上のものが作れる or 作れないの境界値が今回の答えの値。

まず、判定をどうするか。目標を $P^*$ とすれば各容器 $i$ に対し、 $w_i \times (P^* - p_i)$ を求めて、貪欲に大きいものからとって 0以上なら $P^*$ は作れる。0未満なら作れないとやれば良い。
$(実際の食塩の量) = p_i w_i + p_{i+1} w_{i+1} + ...$
$(必要な食塩の量) = P^* \sum w = P^*w_i + P^*w_{i+1} +...$