https://atcoder.jp/contests/abc144/submissions/13628299
- 答え（が条件を満たすかどうか）で二分探索をする
Kが無ければ簡単でAの昇順とFの降順を掛け算するのが最善になる。Kがある場合は値の大きいAを優先して減らせば良いが、求めたい最小値以上に減らすと無駄になって最善でなくなってしまうので、工夫が必要になる。
正しい貪欲を考えるのは困難なので、答えを]の範囲で決め打ちして二分探索して無理やり求める。各乗算は ans = (A[i] - k[i]) × F[i] なので k[i] = A[i] - ans / F[i] となる。二分探索の条件は「kの合計がK以下かどうか」とする。二分探索で得られた範囲のうち最小値が求めたい答えになる。計算量は
になる。
