[UVa]299:Train Swapping

其實就是問Bubble Sort交換的次數...

[C](0.012)

	#include<stdio.h>
	void swap( int *a, int *b )
	{
	(*a) ^= (*b) ^= (*a) ^= (*b);
	}
	int main()
	{
	int N;
	while( scanf( "%d", &N ) != EOF )
	{
	int L;
	int i;
	for( i = 0 ; i < N ; i++ )
	{
	scanf( "%d", &L );
	int order[55] = {0};
	int j;
	for( j = 0 ; j < L ; j++ )
	scanf( "%d", &order[j] );
	int k;
	int swaps = 0;
	for( j = 0 ; j < L ; j++ )
	for( k = L-1 ; k > j ; k-- )
	if( order[k] < order[k-1] )
	{
	swaps++;
	swap( &order[k], &order[k-1] );
	}
	printf( "Optimal train swapping takes %d swaps.\n", swaps );
	}
	}
	return 0;
	}

view raw ACM299.c hosted with ❤ by GitHub