AtCoder Beginner Contest 117 C問題

AtCoder Python

C問題

難易度：茶色

15~20分で解きました。

atcoder.jp

数直線と N個のコマを用いて 1人でゲームを行います。
はじめ、これらのコマをそれぞれ好きな整数座標に置きます。
このとき、同じ座標に複数のコマを置いても構いません。
以下の移動を繰り返して、座標 X1,X2,...,Xmの M個の地点全てをいずれかのコマで訪れることが目的です。
移動: コマを 1 つ選び、そのコマの座標を
xとする。そのコマを座標 x+1もしくは座標 x−1に移動する。
ただし、最初にコマを置いた座標はその時点で訪れたとみなします。
目的を達成するまでに移動を行う回数の最小値を求めてください。

1≤M,N≤100000であり、計算量的に二重ループO(N^2)は許されないです。
この問題を見て、与えられた数直線をSortしたいなあと。

調べてみると、Pythonのsort()はO(N-2)でなく、O(N*logN)なので、
計算量的には間に合いそうです。

コマ数N≥目標座標数Mの場合

目標座標にコマを置いてしまえばいいのですから、移動する必要はありません。
よって0です。

コマ数N<目標座標数Mの場合

  1. まずは目標座標をソートします。
  2. ソートした座標を隣の座標との差分を取る。
  3. 差分をソート。間が短い目標座標ランキングを作成。
  4. 下位(=間が長い)Y(=目標座標数M-(コマ数N-1))ｺ分だけを除く。
  5. 残りを合計するとコマの最短の移動数となる。
N,M = map(int,input().split())
X = list(map(int, input().split()))
 
if N>=M: print(0)
else:
  X.sort()
  delta_X = [X[i]-X[i-1] for i in range(1,M)]
  delta_X.sort()
  print(sum(delta_X[0:M-N]))