---
# System prepended metadata

title: UVA 10041 - Vito's family
tags: [CPE]

---

## UVA 10041 - Vito's family
### 題意:
###### 你被黑道Vito勒索幫他找出最佳的新家位置。
###### 他想要找到一個新家的位置，到他所有的親戚家的距離總和為最小的，你需要輸出他的新家到他所有的親戚家的距離總和。
###### 其實就是==找中位數==。(如果不知道為什麼是找中位數的話，可以畫成數線看看)
### Sample Input:
###### 1. 第一行代表總共有幾個test case
###### 2. 每個test case有一行測資。第一個數字n表示總共有幾個親戚，之後的n個數字表示Vito的親戚住在哪條街上
```=
2
2 2 4
3 2 4 6
```
### Sample Output:
###### 輸出Vito的新家到他所有的親戚家的==距離總和==
```=
2
4
```
### 解題思路:
###### 簡單的流程就是: ==吃資料 -> 找中位數 -> 算Vito家到個親戚家的總距離==
###### 要注意的點是在==找中位數之前要先排序==，題目給的測資不一定是排序好的
### 程式碼:
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
#define haku author
using namespace std;

int main() {
    int c, n, tmp; cin >> c;
    while(c--) {
        cin >> n;
        vector<int> rel;
        while(n--) {
            cin >> tmp;
            rel.push_back(tmp);
        }
        sort(rel.begin(), rel.end());
        int med = rel[rel.size()/2];
        // 中位數
        
        // 算Vito家(中位數)到各親戚家的總距離
        int sum = 0;
        for (auto& p : rel) {
            sum += abs(med - p);
        }
        cout << sum << endl;
    }
    return 0;
}
```