---
title: UVA 10041 Vito’s family
description: CPE 1 星精選題目(CPE10406, UVA10041)，AC 解答與題目解析
image:
tags:
- 解題筆記
- UVA
- CPE
- 程式競賽
---
# UVA 10041 Vito’s family | 解析 | CPE 1 星精選集
**題目連結：** https://onlinejudge.org/external/100/10041.pdf

**平台：**
- [Online Judge](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=982&mosmsg=Submission+received+with+ID+29374919)
- [Zero Judge](https://zerojudge.tw/ShowProblem?problemid=a737)

## 題目解析
有一個黑幫老大 Vito 要去拜訪親戚，要找一間房子，離所有親戚的屋子距離最短。

### Input
- $n$：測資數量
- $r$ $(0<r<500)$：親戚數量
- $s_i$ $(0<s_i<3000)$：街道號碼

第一行會先有一數字 $n$ 代表總共測資的數量。接著會有 $n$ 行測資輸入，每筆測資的第一的數字 $r$ 代表親戚的數量，接著會有 $r$ 個數字 $s_0, s_1,s_2,...,s_{r-1}$ 代表每個親戚所在的街道號碼。

r
n s s s ... s
n s s s ... s
...
n s s s ... s

### Output
找到老大家後，印出老大家到所有親戚家的最短路徑和。
- $distance_{i,j} = |s_i - s_j|$

## 解題思路
由於是給一組數字 $S = \{s_0,s_1,s_2,...,s_{r-1}\}$，然後要找出一個數字 $h$ 對於所有數字的差的和。所以可以整理成以下式子，$sum$ 就是我們最後要輸出的值。

\begin{aligned}
sum &= |h-s_0|+|h-s_1|+|h-s_2|+...+|h-s_{r-1}| \\
&=\sum_{i=0}^{r-1}|h-r_i| \\
\end{aligned}

找到 $h$ 的方法最簡單就是利用中位數的概念。
::: info
<i class="fa fa-info-circle" aria-hidden="true"></i> **中位數**
給定一排序過的集合 $S = \{s_1,s_2,s_3,...,s_n\}$，$S$ 的中位數 $mid$ 為：
- 若 $n$ 是偶數：$mid = s_{\frac{n}{2}}$
- 若 $n$ 是奇數：$mid = (s_{\frac{n}{2}} + s_{\frac{n+1}{2}})/2$
:::

## 實作方式
讀入測資後用 `qsort()` 排序，找出中位數。並依序求到各點的距離和。
### 中位數簡化
若依照原本的敘述進行中位數的實作，程式碼如下：

// odd: size = 5
// 0   1   2   3   4  index
// |---|---|---|---|
// mid = arr[size/2]
//
// even: size = 6
// 0   1   2   3   4   5  index
// |---|---|---|---|---|
// mid = (arr[size/2] + arr[size/2-1]) / 2

int median(int *arr, int size){
    if(size % 2){ // odd number
        return arr[size/2];
    }else{ // even number
        return (arr[size/2] + arr[size/2-1]) / 2;
    }
}

但由於是求到各點距離總和，我們可以簡化一下：

even: size = 4
0   1   2   3   index
|---|---|---|
1   5   10  20  value

假設輸入測資為 $S = \{s_0,s_1,s_2,s_3\}$，其大小 $size = |S| = 4$，中位數 $mid = (s_1+s_2)/2$。
到各點的最短距離和 $sum$：

\begin{aligned}
sum &= |mid-s_0|+|mid-s_1|+|mid-s_2|+|mid-s_3| \\
&=(s_3-s_0)+(s_2-s_1)
\end{aligned}

我們可以發現在中位數對稱的兩項，可以合併在一起。

對所有 $s_i,\ s_j$ 且 $i+j=size-1$
$$
|mid-s_i|+|mid-s_j| = s_j-s_i
$$

就會如下圖所示（$mid$ 用 `o` 表示，`|`　表示 $s_i$、$s_j$）：

even: size = 4
0   1   2   3   index
|---|---|---|
1   5   10  20  value
|-----o-----|
    |-o-|

可以看到，無論 $mid$ 在 $[s_i, s_j]$ 的範圍內的哪個位置，成對的距離相加都不變。但為了要符合 $S$ 中每組成對的距離，$mid$ 只能是 $s_{size/2}$ 或 $s_{s/2-1}$。

也因此可以把中位數的程式簡化成以下：

int median(int *arr, int size){
    return arr[size/2];
}

## 效能
時間複雜度： $O(n \log n)$
> 假設 `qsort()` 實作為 $O(n \log n)$

空間複雜度： $O(n)$

## 程式碼

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        int r;
        scanf("%d", &r);
      
        int street[r];
        for (int i = 0; i < r; i++) {
            scanf("%d", &street[i]);
        }
        qsort(street, r, sizeof(int), cmp);
      
        int sum = 0;
        for (int i = 0; i < r; i++) {
            sum += abs(street[r/2] - street[i]);
        }
      
        printf("%d\n", sum);
    }
}