Day 0x4 UVa10041 Vito's Family

题意

Vito 常拜访亲戚，所以想要找一间和所有亲戚间总距离最小的房子住下来。输入亲戚数和门牌号，输出最小距离和
需要注意的点：
1. 第一行输入为测资数
2. 第二行以後，会先输入第一个数字 r (＜ 500) 代表亲戚数，跟着 r 个数字 S1 ... Sr (＜ 30000)
3. 最小距离要取绝对值

解法

根据国高中学过的神奇数学，中位数和其他点的距离和会最小，这边就交给专业的来解释
- 知乎 - 中位数性质
- YouTube - 绝对值和最小值发生在X为中位数

为了方便解释，用自订 function 来达成每个步骤

因为宣告是区域变数，所以用 Pass By Address 传入

void bubble(int *s, int r);
void swap(int *a, int *b);
void min_distance(int *s, int r);
void sum(int *s, int r, int min);

先读入测资数，再用 while 回圈逐次处理，每次分别先读入亲戚数 r 再用 for 回圈读入各亲戚的门牌号，并存入整数阵列 s (根据 r 的范围，开 500 就够；根据 s 的范围，用 int 宣告)，就可以开始疯狂 call function 了
```
scanf("%d", &num);

while(num--){

    int s[500] = {0};    //the street number

    scanf("%d", &r);
    for(i = 0; i < r; i++){
        scanf("%d", &s[i]);
    }

    bubble(s, r);
}
```

用简单的泡沫排序整理阵列，再继续下一步骤找中位数

void bubble(int *s, int r){

    int i, j;

    for(i = 0; i < r - 1; i++){
        for(j = 0; j < r - 1 - i; j++){
            if(s[j] > s[j + 1]){
                swap(&s[j], &s[j + 1]);
            }
        }
    }

    min_distance(s, r); //find median
}

void swap(int *a, int *b){

    int temp;

    temp = *a;
    *a = *b;
    *b = temp;
}

因为阵列已排序，所以中位数就在中间 (废话XD)，再根据 r 为奇偶数，分别求得中位数
- 偶数 r % 2 == 0
  - 最中间的两个数字相加 ÷ 2
- 奇数
  - 因为阵列的 index 从 0 开始，直接求商即可
```
void min_distance(int *s, int r){

    int min_d = 0;

    if(r % 2 == 0){
        min_d = (s[(r / 2) - 1] + s[(r / 2)]) / 2;
    }
    else{
        min_d = s[(r / 2)];
    }

    sum(s, r, min_d);
}
```
中位数简化
- 因为找中位数後的重点是求总和，所以其实可以不必判断奇偶，为何能这样就留给大家思考罗，可以代数字试试看！
```
void min_distance(int *s, int r){
    sum(s, r, s[(r / 2)]);
}
```
用 for 回圈取每个门牌和中位数的距离，这里可用 abs 函式来取绝对值 (也可 if 判断後大 - 小)，每次更新总和 sum，便可输出最小距离和罗～
```
void sum(int *s, int r, int min){

    int i;
    int sum = 0;

    for(i = 0; i < r; i++){
        sum = sum + abs(min - s[i]);
    }

    printf("%d\n", sum);
}
```

C Code

#include<stdio.h>

void bubble(int *s, int r);
void swap(int *a, int *b);
void min_distance(int *s, int r);
void sum(int *s, int r, int min);

int main(){

    int num;    //number of test case
    int r;      //number of relatives
    int i;

    scanf("%d", &num);

    while(num--){
        int s[500] = {0};   //the street number
        scanf("%d", &r);
        for(i = 0; i < r; i++){
            scanf("%d", &s[i]);
        }
        bubble(s, r);
    }

    return 0;
}

void bubble(int *s, int r){

    int i, j;

    for(i = 0; i < r - 1; i++){
        for(j = 0; j < r - 1 - i; j++){
            if(s[j] > s[j + 1]){
                swap(&s[j], &s[j + 1]);
            }
        }
    }

    min_distance(s, r); //find median
}

void swap(int *a, int *b){

    int temp;

    temp = *a;
    *a = *b;
    *b = temp;
}

void min_distance(int *s, int r){
    sum(s, r, s[(r / 2)]);
}

void sum(int *s, int r, int min){

    int i;
    int sum = 0;

    for(i = 0; i < r; i++){
        sum = sum + abs(min - s[i]);
    }

    printf("%d\n", sum);
}

C++

可以用 vector 等 STL 来存门牌号
内建的 sort 既方便也比泡沫排序快
求总距离和可以用 accumulate 加上 function，但此题感觉没必要，就没使用了

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

int main(){

    int T;  // number of test cases
    int r;  // number of relatives
    int i, temp;

    cin >> T;

    while(T--){

        vector<int> v;
        int MID = 0;
        int SUM = 0;

        cin >> r;

        for(i = 0; i < r; i++){
            cin >> temp;
            v.emplace_back(temp);
        }

        sort(v.begin(), v.end());
        MID = v[r / 2];

        for(i = 0; i < r; i++){
            SUM = SUM + abs(MID - v[i]);
        }

        cout << SUM << endl;
    }

    return 0;
}

<<: Transactions (4) - Concurrent Write

>>: Day 03 | 透过指令建立元件