【AtCoder-Ruby】ABC117 C - Streamline

問題

問題文

数直線と N 個のコマを用いて 1 人でゲームを行います。
はじめ、これらのコマをそれぞれ好きな整数座標に置きます。
このとき、同じ座標に複数のコマを置いても構いません。
以下の移動を繰り返して、座標 X1, X2, ... , XM の M 個の地点全てをいずれかのコマで訪れることが目的です。

移動: コマを 1 つ選び、そのコマの座標を x とする。

そのコマを座標 x + 1 もしくは座標 x − 1 に移動する。
ただし、最初にコマを置いた座標はその時点で訪れたとみなします。
目的を達成するまでに移動を行う回数の最小値を求めてください。

制約

• 入力はすべて整数である。
• 1 ≤ N ≤ 10**5
• 1 ≤ M ≤ 10**5
• − 10**5 ≤ X i ≤ 10**5
• X1, X2, ..., XM は全て異なる。

問題リンク

考えたこと

• 各座標の間の距離が小さいところにコマを置いていけば最小の値が見つかる
• コマを置いた座標は訪れたとみなされるため、座標間の距離が長いところにコマを置けばいい
• ようするに
  • 座標間の差分のリストソート（降順）
  • コマの数 - 1 からのリストの合計が答え

回答

N, M = gets.strip.split.map(&:to_i)
a = gets.strip.split.map(&:to_i).sort

# ds: distances
ds = Array.new(M - 1){0}

(M - 1).times { |i| ds[i] = a[i + 1] - a[i] } 
puts N < M ? ds.sort.reverse[(N - 1)..-1].inject(:+) : 0

考察

今回は自力でとけたので少しホッとした。
少しは、マシになってきた気がする。

参考まで。 けんちょんの競プロ精進記録