A - いっしょ (Together) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

ある 1 本の道に N 匹のビーバーがいる.この道は数直線と見なされ,i 番目 (1 \leqq i \leqq N) のビーバーは座標 X_{i} にいる.

ビーバーは皆寂しがりやなため,自分と同じ座標に他のビーバーが 1 匹以上いると嬉しくなる.

ビーバーを適切に移動させることによって,移動距離の総和をできるだけ小さくしつつ,全員が同時に嬉しくなるようにしたい.なお,移動しないビーバーがいても良い.

N 匹のビーバーの座標が与えられたとき,ビーバーを移動させて全員が同時に嬉しい状態を作るための,ビーバーの移動距離の総和の最小値を求めるプログラムを作成せよ.

なお,この問題の制約の下では,答えは必ず整数になることが証明できる.

入力

入力は以下の形式で標準入力から与えられる.

N
X_{1} X_{2} \cdots X_{N}

出力

ビーバーを移動させて全員が同時に嬉しい状態を作るための,ビーバーの移動距離の総和の最小値を標準出力に 1 行で出力せよ.

制約

  • 2 \leqq N \leqq 100\,000.
  • 1 \leqq X_{i} \leqq 10^{9} (1 \leqq i \leqq N).
  • 入力される値はすべて整数である.

小課題

  1. (17 点) N = 4.
  2. (20 点) X_{i} = i (1 \leqq i \leqq N).
  3. (35 点) N \leqq 100,X_{i} \leqq 100 (1 \leqq i \leqq N).
  4. (28 点) 追加の制約はない.

入力例 1

4
1 2 3 4

出力例 1

2

例えば以下のように移動することで,全員が同時に嬉しくなる.

  • 1 番目のビーバーが座標 1 から座標 2 まで移動する.
  • 3 番目のビーバーが座標 3 から座標 4 まで移動する.

このとき,移動距離の総和は 2 であり,移動距離の総和をこれ以上小さくすることはできないため,2 を出力する.

この入力例はすべての小課題の制約を満たす.

入力例 2

5
1 9 8 2 7

出力例 2

3

例えば以下のように移動することで,全員が同時に嬉しくなる.

  • 1 番目のビーバーが座標 1 から座標 2 まで移動する.
  • 5 番目のビーバーが座標 7 から座標 8 まで移動する.
  • 2 番目のビーバーが座標 9 から座標 8 まで移動する.

このとき,移動距離の総和は 3 であり,移動距離の総和をこれ以上小さくすることはできないため,3 を出力する.

この入力例は小課題 3, 4 の制約を満たす.

入力例 3

10
9 20 5 10 8 1 10 19 15 4

出力例 3

10

この入力例は小課題 3, 4 の制約を満たす.


Source Name

JOIG 2023/2024 春季トレーニング Contest Day1