きろく

特筆すべき記録のまとめ

AtCoder Beginner Contest 127:D - Integer Cards

問題

atcoder.jp

解法

M 回の操作は順序を入れ替えても問題ないので,C_i が大きい順に行っていくのがよい.また,A_i を小さい順に操作するかどうかを決めていく.今見ている操作が i 番目で今見ている要素が j 番目のとき,C_i が A_j より大きければ A_j を C_i で置き換える操作をする.そうでなければ,置き換えてしまったら総和が小さくなってしまうのでその時点で操作をやめて,この時点での A を答えとすればよい.なぜならば, i + 1 番目以降の操作の C は C_i より小さいため,A_j を置き換えることができないから.逆に,C_i > A_j となっている限りは最大 B_i 回操作を行えばよい.O(NlogM).

解答

atcoder.jp

f:id:babcs2035:20190602215514p:plain