UVA 10041 Vito’s family | 解析 | CPE 1 星精選集

題目連結： https://onlinejudge.org/external/100/10041.pdf

平台：

• Online Judge
• Zero Judge

題目解析

有一個黑幫老大 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

找到老大家後，印出老大家到所有親戚家的最短路徑和。

• $distanc{e}_{i,j}=|s_i-s_j|$

解題思路

由於是給一組數字

$S=\{s_0,s_1,s_2,...,s_{r-1}\}$，然後要找出一個數字

$h$ 對於所有數字的差的和。所以可以整理成以下式子，

$sum$ 就是我們最後要輸出的值。

$$\begin{array}{rl}sum& =|h-s_0|+|h-s_1|+|h-s_2|+...+|h-s_{r-1}|\\ & =\sum _{i=0}^{r-1}|h-r_i|\end{array}$$

找到

$h$ 的方法最簡單就是利用中位數的概念。

中位數
給定一排序過的集合

$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{array}{rl}sum& =|mid-s_0|+|mid-s_1|+|mid-s_2|+|mid-s_3|\\ & =(s_3-s_0)+(s_2-s_1)\end{array}$$

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

對所有

$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);
    }
}