/
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).
- 入力される値はすべて整数である.
小課題
- (17 点) N = 4.
- (20 点) X_{i} = i (1 \leqq i \leqq N).
- (35 点) N \leqq 100,X_{i} \leqq 100 (1 \leqq i \leqq N).
- (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 の制約を満たす.