No.609 Noelちゃんと星々

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 165
作問者 : Lemma299Lemma299 / テスター : sei0osei0o
7 ProblemId : 2000 / 出題時の順位表
問題文最終更新日: 2017-12-09 02:30:59

この問題はAdvent Calendar Contest Advent Calendar 2017の9日目の問題です.

問題文

点がN個あたえられます, 点iの高さは$Y_i$です, Noelちゃんは点の高さを自由に動かせます.
ある日Noelちゃんは全ての点を同じ高さに揃えたくなりました.
Noelちゃんが動かす必要のある距離の総和の最小値を求めてください.

入力

$ N $
$ Y_1\ Y_2\ \cdots\ Y_{N-1}\ Y_N $

1行目に点の数 $N(1\le N\le 10^5) $ が与えられます.
2行目に$N$個の整数 $ Y_i(-10^9 \le Y_i \le 10^9) $ が与えられます.

追記 12/9 0:47 制約が$N(1\le N\le 10^5) $に変更されました。

出力

距離の総和の最小値を整数で出力してください.

追記 12/9 0:57 整数での出力に変更しました.

サンプル

サンプル1
入力
5
5 7 5 7 7
出力
4

高さ$7$に揃えると $2+0+2+0+0=4$ で最小になります.

サンプル2
入力
11
-1000000000 -1000000000 -1000000000 -1000000000 -1000000000 0 1000000000 1000000000 1000000000 1000000000 1000000000
出力
10000000000

答えが32bit整数に収まらないこともあります.

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。