CODE FESTIVAL 予選A D.壊れた電車

問題

N車両の電車をM人で点検する。最初、i番目の人はXi車両目にいる。
点検には時間がかからないが、隣の車両への移動には1分かかる。
すべての車両を少なくとも1人が点検した状態にするのにかかる時間は最低何分か？

1<=N<=10^9
1<=M<=10^5, M<=N

考え方

Nが大きいので、車両の状態を配列とかに持ってループを回すのは無理。

各人がどの範囲を点検するかを考えると、一番左にいる人は左側に車両があるなら、そこを点検しないといけない。二番目に左にいる人は一番左の人が点検していないところから点検しないといけない。と、貪欲に決められる。
点検に使える時間tが決まれば、上記のように貪欲に決めていけるので、二分探索で、時間を求めればよい。

ただし、点検する範囲は、左側は「一つ左の人の点検しなかったところ」から点検しないといけないが、右側はどこまで点検できるかというと、、サンプルにある通り、「左に行ってから右に行けるだけ行く」場合と「右に行ってから左に行く」場合があって、そのどちらかできるだけ右側まで点検できる方法で点検する必要がある。
「右に行ってから左に行く」場合は、どこまで左に行けるかというと、(t-(Xi-{左の人が点検していない車両}))/2までなら右に行ってから左の点検していないところまでたどり着ける。