• Virtual Judge
• ZeroJudge

題意

• 輸入 n 個數字，輸出能使 (|X1 − A| + |X2 − A| + . . . + |Xn − A|) 得到最小值的 A、最小值數量與最小值有幾種
• 需要注意的有：
  1. 每筆測資都先輸入 n 個數字 (0 < n ≤ 1000000)
  2. 後面的 n 行為式子中的 x

解法

• 和 Day 0x4 UVa10041 Vito's Family 13th鐵人賽 uva c c++ 一顆星選集 有 87% 像

  所以一樣教給專業來解釋
  絕對值和最小值發生在X為中位數
  代表說輸出需要的 A 即為中位數

• 透過 while 重複讀入代表有多少數字的 n，再用 for 存 n 個數字到陣列裡，因為泡沫排序效率太低 (n 有可能很大)，就用內建的 qsort 來優化

  int x[1000000];
  
  int compare(const void *a, const void *b){
      return(*(int*)a - *(int*)b);
  }
  
  int main(){
  
      int n;
      int i, j;
  
      while(scanf("%d", &n) != EOF){
  
          for(i = 0; i < n; i++){
              scanf("%d", &x[i]);
          }
  
          qsort(x, n, sizeof(int), compare);
  
          ...
      }
  
      return 0;
  }
  

• 排序好後即可找中位數，因為有可能 n 的奇偶問題，用兩個變數 A1、A2 來分別賦值，至於為什麼這樣寫也留給大家代數字思考看看囉；找好中位數就開始用 for 迴圈計算最小值數量，並用 A2 - A1 + 1 求得有幾種最小值

  A1 = x[(n - 1) / 2];
  A2 = x[n / 2];
  count = 0;
  
  for(i = 0; i < n; i++){
      if(x[i] == A1 || x[i] == A2){
          count++;
      }
  }
  
  printf("%d %d %d\n", A1, count, A2 - A1 + 1);
  

• C code

  #include<stdio.h>
  #include<stdlib.h>
  
  int x[1000000];
  
  int compare(const void *a, const void *b){
      return(*(int*)a - *(int*)b);
  }
  
  int main(){
  
      int n;
      int A1, A2;
      int count;
      int i, j;
  
      while(scanf("%d", &n) != EOF){
  
          for(i = 0; i < n; i++){
              scanf("%d", &x[i]);
          }
  
          qsort(x, n, sizeof(int), compare);
  
          A1 = x[(n - 1) / 2];
          A2 = x[n / 2];
          count = 0;
  
          for(i = 0; i < n; i++){
              if(x[i] == A1 || x[i] == A2){
                  count++;
              }
          }
  
          printf("%d %d %d\n", A1, count, A2 - A1 + 1);
      }
  
      return 0;
  }