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