# TIOJ-1732.買當勞

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

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

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

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

## Input&Output Format、Sample

**Input:**

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

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

n <= 100000

(Sample)
1
3
2
1 2
4
12 7 -13 100

**Output:**

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

(Sample)
0
1
118
## AC code及思路

**想法:**
Greedy演算法，將麥當勞的位置設於中位數，即可得到最小的距離和。

**AC code:**

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, a, mid, ans;
vector <int> v;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while (cin >> n){
        v.clear();
        for (int i = 0; i < n; i++){
            cin >> a;
            v.push_back(a);
        }
        sort(v.begin(), v.end());
        ans = 0;
        mid = v[n/2];
        for (int i = 0; i < n; i++){
            ans += abs(v[i]-mid);
        }
        cout << ans << "\n";
    }
}