15/09/29 09:20:10.07 .net
次に4分で全部点検できるかを判定する。
123456789abc
1 2 3
まず1番の人は左1右3と移動する。
123456789abc
1111 2 3
次に2番の人は右1左3と移動する。
123456789abc
111122223
次に3番の人は右4移動する。
123456789abc
111122223333
よって4分あれば車両をすべて点検できる。
注意として2番の人が左2右2と移動すると
123456789abc
1111222 3
となり、全部を点検できなくなる。
左に行って右だけでなく、右に行って左のケースも考慮しなければならない。
加えて、左右左や右左右のような移動は明らかに無駄なので考えなくてよい。
k分で点検できるなら、k+1分でも点検可能なので、二分探索で最小のkを求めることができる。O(MlogN)