[UVa] 299 - Train Swapping

只能左右交換的排序

以陣列來看，在第 i 個位置，向右找到和自己位置相同的數字

一直向左交換回來即可 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int train[70]; //train carriages
int main(){
  memset(train,0,sizeof(train));
  int n; //cases
  scanf("%d",&n);
  while(n--){
    int L; //length of traiin
    int count=0; //swap count
    scanf("%d",&L);
    for(int i=0;i<L;i++)scanf("%d",&train[i]); 
    for(int i=0;i<L;i++){
      for(int j=i;j<L;j++){
        if(train[i] == i+1)break;
        if(train[j] == i+1){  //左右交換
            int tmp = train[j];
            train[j] = train[j-1];
            train[j-1] = tmp;
            j=i;
            count++;
        }  
      }
    }
    //for(int i=0;i<L;i++)printf("%d ",train[i]);    
    //printf("\n");
    printf("Optimal train swapping takes %d swaps.\n",count);
  }

  return 0;  
}