---
# System prepended metadata

title: Vito's family(UVA10041)
tags: [CPE一顆星必考題]

---

# Vito's family(UVA10041)
## [程式繳交區](https://hackmd.io/@Renektonn/SJersqqPJl/edit)
## 題目
[點我](https://onlinejudge.org/external/100/10041.pdf)

## 解題系統
[UVA](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=982)
[ZJ](https://zerojudge.tw/ShowProblem?problemid=a737)

## 解法
求中位數，因為是中位數到所有點的距離總和是最小的。
## 演算法
```
1.輸入整數t
2.判斷t是否小於等於0，若是，則結束
3.輸入整數r，代表ri個的個數
4.將給定的數字ri由小到大排序，並找出中位數m，m用double型態
3.算出m與所有ri的距離和sum，並印出sum，但不要印出小數點
5.t=t-1並回到2
```

## 程式碼
```cpp=
/*
0 < r < 500
0 < si < 30000
*/
#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;

    while (t > 0) {
        int r;
        cin >> r;
        if (r <= 0) {
            t--;
            continue;
        }

        vector<int> ri(r + 1); // 調整為 r + 1，使索引從 1 開始
        for (int i = 1; i <= r; ++i) { // 從索引 1 開始讀入
            cin >> ri[i];
        }

        // 排序（只排序有效範圍）
        sort(ri.begin() + 1, ri.end());

        // 找中位數
        double m;
        if (r % 2 == 1) {
            m = ri[(r + 1) / 2]; // 當 r 是奇數，使用 (r + 1) / 2
        } else {
            m = (ri[r / 2] + ri[r / 2 + 1]) / 2.0; // 當 r 是偶數
        }

        // 計算距離和
        double sum = 0;
        for (int i = 1; i <= r; ++i) { // 計算距離
            sum += abs(ri[i] - m); // 不進行 round(m)
        }

        // 強制型轉為 int 輸出
        cout << (int)sum << endl;

        // 減少測試次數
        t--;
    }

    return 0;
}

```

