ABC034 ~食塩水~

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} +...

判定ができれば、あとは境界値を探れば良い。

ソースコード
Submission #2374269 - AtCoder Beginner Contest 034


まとめ :
 max(\dfrac{\sum v}{\sum w}) を求めるのは典型 ! 二分探索 + 貪欲