Day 0x13 UVa299 Train Swapping

• Virtual Judge
• ZeroJudge

题意

• 输入火车的排列状态，输出需要交换多少次以排好顺序
• 需要注意的有：
  1. 输入第一行一个整数 N 代表测资数
  2. 每笔测资第一行 L 代表火车长度 (0 ≤ L ≤ 50)
  3. 每次交换只能对调相邻两车厢
  4. 输出格式
     • Optimal train swapping takes S swaps.

解法

• 输入测资数 N 并用 while 回圈重复，再读每笔测资长度 L 并存入整数阵列中

  int N;
  int L;
  int train[50] = {0};
  
  scanf("%d", &N);        //number of case
  
  while(N--){
  
      scanf("%d", &L);    //length of train
  
      for(i = 0; i < L; i++){
          scanf("%d", &train[i]);
      }
      ...
  }
  

• 因为 L 的范围很小，所以用泡沫排序的概念计算交换次数即可 (一星题嘛 XD)
  • 若测资范围变大，就需要逆序数对的概念
  • Ultra-QuickSort

  int count = 0;
  
  for(i = 0; i < L - 1; i++){
      for(j = 0; j < L - 1 - i; j++){
          if(train[j] > train[j + 1]){
              temp = train[j];
              train[j] = train[j + 1];
              train[j + 1] = temp;
              count++;
          }
      }
  }
  
  printf("Optimal train swapping takes %d swaps.\n", count);
  

• C code

  #include<stdio.h>
  
  int main(){
  
      int N;
      int L;
      int train[50] = {0};
      int i, j;
      int temp;
  
      scanf("%d", &N);        //number of case
  
      while(N--){
  
          scanf("%d", &L);    //length of train
  
          int count = 0;
  
          for(i = 0; i < L; i++){
              scanf("%d", &train[i]);
          }
  
          for(i = 0; i < L - 1; i++){
              for(j = 0; j < L - 1 - i; j++){
                  if(train[j] > train[j + 1]){
                      temp = train[j];
                      train[j] = train[j + 1];
                      train[j + 1] = temp;
                      count++;
                  }
              }
          }
  
          printf("Optimal train swapping takes %d swaps.\n", count);
  
      }
  
      return 0;
  }