所求即是做泡沫排序法時所交換的次數。
C++(0.012)
/*******************************************************/ /* UVa 299 Train Swapping */ /* Author: LanyiKnight [at] knightzone.org */ /* 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; }