iT邦幫忙

2021 iThome 鐵人賽

DAY 4
0
自我挑戰組

用 C & C++ 帶你手把手解 UVa 一顆星選集系列 第 4

Day 0x4 UVa10041 Vito's Family

Virtual Judge
ZeroJudge

題意

  • Vito 常拜訪親戚,所以想要找一間和所有親戚間總距離最小的房子住下來。輸入親戚數和門牌號,輸出最小距離和
  • 需要注意的點:
    1. 第一行輸入為測資數
    2. 第二行以後,會先輸入第一個數字 r (< 500) 代表親戚數,跟著 r 個數字 S1 ... Sr (< 30000)
    3. 最小距離要取絕對值

解法

  • 根據國高中學過的神奇數學,中位數和其他點的距離和會最小,這邊就交給專業的來解釋
  • 為了方便解釋,用自訂 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;
    }
    

上一篇
Day 0x3 UVa10222 Decode the Mad man
下一篇
Day 0x5 UVa10062 Tell me the frequencies!
系列文
用 C & C++ 帶你手把手解 UVa 一顆星選集30

尚未有邦友留言

立即登入留言