競技プログラミング用 知識集積所
ABC443D - Pawn Line
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
- 特になし
考え方
全ての駒について、「最低でもこの位置より上にいなければならない」の位置を求める。
これは、
これは、
- 元々いる位置よりは上でなくてはいけない
- 隣のやつより1つ下、よりは上でなくてはいけない
を満たすようにすればよく、priority_queue※などを使って高い位置にある制約から順に処理していくことで求められる。
あとは各駒ごとに移動する距離を出せばよい。
解答例
注意点
long long型を使う。
駒を上下に散らされると、答えがint型の範囲を超えてしまう。
