#UVa:299-Train Swapping

灆洢 2012-03-14 15:56:59

所求即是做泡沫排序法時所交換的次數。

C++(0.012)

/*******************************************************/
/* UVa 299 Train Swapping                              */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2012/03/14                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
using namespace std;

int main(){
  int testcase;
  int L, swap_num;
  int train[55];
  while( scanf( "%d", &testcase ) != EOF ){
    for( int i = 0 ; i < testcase ; i++ ){
      scanf( "%d", &L );
      for( int j = 0 ; j < L ; j++ )
        scanf( "%d", &train[j] );

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

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料