競技プログラミング用 知識集積所
ABC437D - Sum of Differences
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
愚直に和を計算すると、MN回の計算が必要でTLE。
よって、高速化を考える必要がある。
よって、高速化を考える必要がある。
絶対値を「大きい方を足して小さい方を引く」と考える。
Aのそれぞれの値は、「Bの中で自分より大きい数の分だけ引き算して、自分より小さい数の分だけ足し算する」ということになる。
Bの方も同様。
（AとBに同じ数があった場合は、両方を無視するか、適当なルールで大小をつける）
すると、AとBの組み合わせごとMN回ではなく、AのそれぞれごととBのそれぞれごとのM+N回の処理でいけることになる。
Aのそれぞれの値は、「Bの中で自分より大きい数の分だけ引き算して、自分より小さい数の分だけ足し算する」ということになる。
Bの方も同様。
（AとBに同じ数があった場合は、両方を無視するか、適当なルールで大小をつける）
すると、AとBの組み合わせごとMN回ではなく、AのそれぞれごととBのそれぞれごとのM+N回の処理でいけることになる。
実装方法はいくつかあるが、AとBそれぞれをpriority_queue※につめて、2つのtopの値が大きい方に処理していくのが楽か。
この場合、今の相手のpriority_queue※のサイズを見れば、何回足して何回引くかをすぐに求められるし、同じ数があった場合のタイブレークも自然に組み込まれる。
この場合、今の相手のpriority_queue※のサイズを見れば、何回足して何回引くかをすぐに求められるし、同じ数があった場合のタイブレークも自然に組み込まれる。
