from ABC181 ABC181E
- 考えたこと
- 数のペアの差の合計の最小化をしたいが、ある一つの数XだけM通りに変えられる
- Mは10^5以上あるので全部試すのはむずかしい？
- 差の合計が定数か対数オーダーで求まるならよい
- 差の合計について考える
- ペアを範囲として捉えた時にオーバーラップがあるなら、交換して差をもっと小さくできるから区間が交わらないとしてよい
- となると貪欲に小さい方からペアにしていったものが最適解
- 値の変わるものを除いて、上からペアにした累積和と下からペアにした累積和を作る
- 左右から累積積と同じ発想
- Xが何番目に入るのかを二分探索で求める、対数オーダー
- Xは奇数個の方に入れる、それぞれ累積和で定数オーダー
- 公式解説OK
- しゃくとり法で解く選択肢もある