[CPE一星49題] UVA10041 - Vito's Family 題目解析與實作

編輯製作： 蔡豐聲、莊祺仁

單位： 中國醫藥大學醫療資訊學系程式俱樂部

YT： https://youtu.be/qApzJsc6n0U

## 題目資訊

題目名稱： Vito's Family

編號： CPE10406, UVA10041

相關平台： Zero Judge, Online Judge

## 題目解析

世界聞名的黑社會老大 Vito Deadstone 要搬到紐約來了。在那裡他有一個大家族，並且他們都住在 Lamafia 大道上。因為 Vito 時常要拜訪所有的親戚，他想要找一間離他們最近的房子，也就是說他希望從他的家到所有親戚家的距離總和為最小。

核心目標： 在一條直線上找到一個點（房子位置），使得該點到所有給定點（親戚家）的距離之和最小。

## 輸入說明

第一列有一個整數，代表共有多少組測試資料。

每組測試資料一列：

第一個整數 $r$ ($0 < r < 500$)：代表親戚的數目。
接下來的 $r$ 個整數 $s_1, s_2, \dots, s_r$：代表這些親戚房子的門牌號碼 ($0 < s_i < 30000$)。
注意：有些親戚的門牌號碼可能會相同。

## 輸出說明

對每組測試資料，輸出 Vito 住所到所有親戚家最短的距離總和。

## 範例測試

輸入：

2 2 4

3 2 4 6

輸出：

## 解題思路

中位數原理：

要使點到所有點的距離和最小，最理想的地點就是這些座標的中位數 (Median)。

步驟：

將所有親戚的門牌號碼進行排序。
找出中位數（若親戚數為奇數，取中間值；若為偶數，取中間兩數任一皆可）。
計算每個門牌號碼與中位數的距離差之絕對值，並加總。

## 實作程式碼 (Python)

import sys

# 第一步
test_cases = int(sys.stdin.readline())

# 第二步
for _ in range(test_cases):
    # 第二之一步
    line = list(map(int, sys.stdin.readline().split()))
    
    # 第二之二步
    r = line[0]
    locations = line[1:]
    
    # 第二之三步
    locations.sort()
    
    # 第二之四步
    mid = locations[r // 2]
    
    # 第二之五步
    # ans = sum(abs(x - mid) for x in locations)
    # 你也可以這麼寫
    ans = 0
    for x in locations:
        ans += abs(x - mid)
        
    print(ans)

---

本著作採用創用 CC 姓名標示-非商業性-禁止改作 3.0 台灣授權條款授權。

本部落格的免責聲明。

程式俱樂部YT頻道 https://www.youtube.com/@tsai-cai

搜尋此網誌

中國醫藥大學蔡豐聲