ABC144 E - Gluttony
問題
$ 1 \leq N \leq 2 \times 10^5
$ 0 \leq K \leq 10^{18}
$ 1 \leq A_i \leq 10^6 (1 \leq i \leq N)
$ 1 \leq F_i \leq 10^6 (1 \leq i \leq N)
が与えられます。負にならない限り$ A_iから好きなように合計$ K減らすことができます(修行)。
その後$ Aと$ Fをマッチングして、積の最大値がスコアになります。
スコアを最小化すると、その値はいくつでしょうか。
解答
まず、修行を抜きにして考えます。
このときスコアが最小化になるのは$ A,$ Fをそれぞれ昇順と降順にソートした場合です。(昇降は逆でも良い)
なぜなら、もし上の条件を満たさない部分がある、つまりある$ i , j (i \lt j)があって$ A_i \gt A_jかつ$ F_i \geq F_jであるとします。
すると
$ A_i \gt A_jから $ A_i F_i \gt A_j F_i
$ F_i \geq F_jから $ A_i F_i \geq A_i F_j
したがって$ A_i F_i = \max(A_i F_i, A_j F_j) \geq \max(A_j F_i, A_i F_j)
なので、$ A_i,$ A_jを交換することで、スコアは変わらないか小さくなります。
交換を繰り返すことで示したい状態に達します。
あるスコアの目標値$ mを決めたとします。$ K回以下の修行回数でスコアを$ m以下にできるか、と考えると、これは$ mに関して単調になり二分探索が使えます。 $ Aを昇順にソートしておき、$ A_i \rightarrow A'_i = \min(A_i, \lfloor \frac{m}{F_i} \rfloor)とします。
このとき
スコアは$ m以下です
$ A'は昇順にソートされた状態(=単調非減少)です
なぜなら
$ F_iが単調非増加なので$ \lfloor \frac{m}{F_i} \rfloorは単調非減少です
$ A_iも単調非減少なので、$ \minをとった$ A'も単調非減少です
修行回数は、値の集合として$ A'になるような最小の修行回数です
なぜなら
もし$ A_i \rightarrow A'_k, $ A_j \rightarrow A'_lで$ A'_k \gt A'_lとなった場合
余分に修行をすることなく$ A_i \rightarrow A_l', $ A_j \rightarrow A_k'になるように修行の割当を換えることができます
$ A_i \rightarrow A_l'は$ A'_l \lt A'_k \leq A_iなので修行可能
$ A_j \rightarrow A_k'は $ A'_k \leq A_i \leq A_jなので修行可能
修行回数は$ A_i + A_j - A'_l - A'_kで変わらない
これを繰り返すことで修行回数を増やすことなく$ A_i \rightarrow A'_iになるような修行回数の割り振りをできます
このように修行をしたとき、修行回数が$ K回以下かどうかが確かめたいことです。
計算量
最初のソートで$ O(N \log N)
二分探索は1回の判定に$ O(N)かかるので、$ Xを答えの値とすると$ O(N \log X)
なので$ O(N \log N + N \log X)です。