AtCoder Beginner Contest 144 E - Gluttony

https://atcoder.jp/contests/abc144/tasks/abc144_e

積の最大値を $x$ 以下にできるかどうかを二分探索する。$F_i$ は降順に並んでいるものと仮定する。このとき各 $F_i$ と対となる値は $\lfloor x/F_i \rfloor$ 以下になるはずである。

よって$A$ を自由に並び替えていいとき $\sum_{i=1}^{N} \max(0, A_i - \lfloor x/F_i \rfloor)$ としてありうる最小の値を求める問題が解ければいい。この最小の値が $K$ 以下ならば $x$ 以下にすることができる。結論をいうと、この値を最小にするには $A_i$ を昇順に並べるのがいい。そのことは以下のような図から分かる（操作後の大小関係が入れ替わるものはもっと値を小さくできるから大小関係が入れ替わる操作がいらない旨を示す図がこの次に入る）。

二分探索の各判定に $O(N)$ 掛かるので全体の計算量は $O(N \log (\max A_i \max F_i))$ である。

---

ずっと積の最大値じゃなくて和を最小化する問題だと思ってたんだけど、サンプル３を見つめていたら答えが１２になるはずがなくて勘違いに気がついた。

---

We can find the maximum product $x$ by using binary search. Suppose that $F_i$ are sorted in descending order. Then, the value correspond to $F_i$ is must be less than or equal to $\lfloor x/F_i \rfloor$.

Therefore, we only have to solve this problem: We can rearrange the array $A$ arbitrarily, then please find the minimum possible $\sum_{i=1}^{N} \max(0, A_i - \lfloor x/F_i \rfloor)$. If this value is smaller or equal to $K$, we can achieve $x$. Actually, if A is sorted in ascending order, this value becomes the minimum. That's why if the order of $A_i$ and $A_j$ are switched, we can construct more efficient solution by swapping the role of the both.

Each check in binary search can be done in $O(N)$, so the entire time complexity is $O(N \log \square)$.