Virtual Judge
ZeroJudge

題意

• 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;
  }