Day 0x10 UVa10057 A mid-summer nights dream

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