3038

同一直線状にあるN点について、同一の方向に進もうとしている集団が、開始位置と目的地と人数の組で与えられる。C人収容できる乗り物が同じ向きに進むとき、一度端から端まで移動する間に運ぶことのできる最大人数を答えよ、という問題。

取り敢えず開始位置と目的地で辞書順にソートする。現在乗っている人数と、目的地別の人数を覚えておき、余裕があれば乗せる。余裕がない場合は、より遠くに行こうとしている人を乗せたことにする。できる遠くに行こうとしている人から追い出す必要がある。

目的地として可能な位置をPriorityQueueに入れておいて、適切にアップデートという実装をした。(これに類することをしないと多分TLEすると思う。)