UVA 10041 - Vito's Family - StackPenguin 部落格

題目描述

Vito 的家族住在同一條街上，但每個人的住址可能不同。Vito 想找到一個住址，使得該住址到家族成員所有住址的總距離最小。給定每位家族成員的住址，找出這個最佳的住址，並計算最小總距離。

解題思路

本題的核心在於如何選擇一個最佳住址，使得所有成員到該住址的總距離最小。最佳的住址是所有家族成員住址的中位數，因為中位數在統計學中能最小化絕對差距的總和。

步驟：

輸入測試案例數量。
輸入家族成員數量與其住址。
對住址進行排序，找出中位數作為最佳住址。
計算每個住址與中位數之間的距離總和。
輸出最小總距離。

程式碼

1
#include <iostream>
2
#include <algorithm>
3
#include <vector>
4
using namespace std;
5

6
int main()
7
{
8
    int testCases;
9
    cin >> testCases;
10

11
    while(testCases--) {
12
        int numRelatives;
13
        cin >> numRelatives;
14

15
        vector<int> addresses(numRelatives);
16
        for(int i = 0; i < numRelatives; i++) {
17
            cin >> addresses[i];
18
        }
19

20
        // 排序住址，找到中位數
21
        sort(addresses.begin(), addresses.end());
22
        int medianAddress = addresses[numRelatives / 2];
23
        int totalDistance = 0;
24

25
        // 計算總距離
26
        for(int i = 0; i < numRelatives; i++) {
27
            totalDistance += abs(addresses[i] - medianAddress);
28
        }
29

30
        // 輸出結果
31
        cout << totalDistance << endl;
32
    }
33

34
    return 0;
35
}