UVa 10041 - Vito’s Family

( Tip: 點擊左上方的三橫槓選單按鈕，可以收起左側 Pdf 頁。)

Step 1. 題目概要

本題的目標是輸出從 Vito Deadstone 的新家到所有親戚家的最小距離和為多少。
- 輸入測資的第一列有一個整數，代表接下來有幾組測資。
- 每組測資的第一個整數r代表親戚的數目。 (0 < r < 500)
- 接下來的r個整數 (s1,s2,…,sr) 代表各個親戚的門牌號碼。(0 < s < 30000)。
注意，親戚的門牌號碼可能會相同。

Step 2. 解題思路

本題的核心觀念為找出 「中位數」，即 Vito Deadstone 的新家，因為中位數到其他各點的距離和為最小。

中位數(Median) ：是指一組數字的中間數字；即是有一半數字的值大於中位數，而另一半數字的值小於中位數。例如：
Case1：5、6、11、315、680 的中位數為 11
Case2：1、2、5、7、15、21 的中位數為 6

提示：Case2 中，中位數取5 or 6 or 7，這三個點分別到各點的距離和都是最小的，也因此程式碼mid = v[r/2]即可產出中位數，無須判斷奇偶之總共有幾個數字，

Step 3. 範例輸入與輸出 - Sample Input and Output

1
2
3

2
2 2 4
3 2 4 6

1
2

2
4

Extra Sample Input
Extra Sample Output

uDebug 快速連結
 Diffnow (線上比對程式)
C++ Online Compiler
Python Online Compiler

Step 4. 參考程式碼 - Accepted Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T;  //Testcases
    cin>>T;
    while(T--) {
        int r;  //親戚的數目
        cin>>r;

        int v[501]={};  //用來裝親戚住的街址
        int res=0;  //results

        for(int i=0;i<r;i++) {
            cin>>v[i]; 
        }

        sort(v,v+r);  //升序排列
        int mid=v[r/2];  //主角要住在中位數的地方

        for(int i=0; i<r; i++) {
            res+=abs(mid-v[i]);
        }
        cout<<res<<"\n";
    }
    return 0;
}