AtCoder Beginner Contest 117:C - Streamline
問題
解法
まず,駒を +1 の方向に動かした後に -1 の方向に動かすのは自明に意味がない.なので,駒を +1 の方向にだけ動かすことを考える.駒が通る距離を最小化したいので,駒が通らない距離を最大化すればよい.一番左・右の地点より外側のところに駒を置くのは自明に意味がないので,駒が通る最大の距離は一番左・右の地点の間の距離となる.ここで,隣り合う地点間の距離をすべて求める.すると,これらの距離のうち大きいもの (N - 1) 個を駒が通らないようにすれば題意を満たせる.駒が地点の数以上にある時に注意.O(MlogM).
解答