10041 Vito’s family

題目連結

題目敘述

世界知名的黑幫份子 Vito Deadstone 即將搬到紐約。他在那裡有一個非常龐大的家族，全都住在 Lamafia 大道上。由於他會經常拜訪所有的親戚，他正在尋找一間靠近他們的房子。

Vito 想要讓他到所有親戚家的總距離最小化，並且已經用恐嚇手段逼你寫一個程式來解決這個問題。

輸入格式

輸入包含數筆測資。第一行是一個整數，表示測資的數量。

對於每一筆測資，你會得到一個整數 r（0 < r < 500），代表親戚的人數，以及他們的門牌號碼（整數）s1, s2, ..., si, ..., sr，表示他們住在街道上的哪個位置（0 < si < 30000）。請注意，可能有多個親戚住在同一個門牌號碼上。

輸出格式

對於每一筆測資，你的程式必須輸出一行，顯示從最適合的 Vito 的新家到他所有親戚家的最小總距離。 兩個門牌號碼 si 與 sj 間的距離定義為： dij = |si − sj|

解題思路

有 t 組測資，給你 r 個整數 s1, s2, . . ., sr ，請找出與 s[i] 最小的距離和。

排序 s[i] ，取中位數，並計算 s[i] 與中位數差之和。 若 r 為偶數，中位數落在中間兩數形成的區間，取 s[(r − 1) / 2] 即可，總距離仍為最小。

程式碼

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

int main() {
    int t, r;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> r;
        int s[r], median, ans = 0;
        for (int j = 0; j < r; j++) {
            cin >> s[j];
        }
        sort(s, s + r) ;
        median = s[(r - 1) / 2];
        for (int j = 0; j < r; j++) {
            ans += abs(s[j] - median);
        }
        cout << ans << '\n';
    }
}