TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

100.0% (87/87)

Submission's AC Ratio

49.7% (142/286)

Tags

Description

在一條無線長的路上住著一些人,
可以把這條路想成一條數線, 這些人所在的位置就是一些整數

買當勞想要在這條路上開一家店,
買當勞可以在任何一個位置開店 (即使那個位置原先有住人)
不過買當勞希望可以選一個好位置, 使得大家來到這邊平均來說是最方便的
所謂最方便指的是, 每個人來到買當勞需要走的距離總和最小

例如如果有四個人分別住在 12, 7, -13, 100 這四個位置
那買當勞可以考慮在 10 這個位置開店
這樣第一個人(12)要走得距離是 2
  第二個人(7)要走得距離是 3
  第三個人(-13)要走得距離是 23
  第四個人(100)要走得距離是 90
距離總就是 2 + 3 + 23 + 90 = 118, 這是一個最小的方案。

現在告訴你總共有 n 個人,
並分別給你他們在這條路上的位置
請問在最佳情形下, 所有人走到買當勞的距離總和最小是多少?

Input Format

輸入有多組測試資料!! 以EOF作為結尾。

每組測試資料第一行有一個整數 n
接下來一行有 n 個整數, 代表這 n 個人的位置。

n <= 100000

Output Format

輸出一個整數代表最小距離總和。
你可以假設答案距離總和不會超過 int 範圍。

Sample Input 1

1
3
2
1 2
4
12 7 -13 100

Sample Output 1

0
1
118

Hints

Problem Source

原TIOJ1732 / kelvin

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1