UVa : 299 (Train Swapping)


Data type:
Long Integer / Integer

Algorithm:
Use bubble sort. Each time swapping block executes then Count++.
Output Count

Critical Input:
2
10
1 1 1 1 1 1 1 1 1 100
9
9 2 4 6 8 1 5 3 2

Critical Output:
Optimal train swapping takes 0 swaps.
Optimal train swapping takes 23 swaps.


#include <stdio.h>

int main ()
{
	long Case, A[52], Num, Count, I, J, Temp;

	//freopen ("229in", "r", stdin);
	//freopen ("229out", "w", stdout);

	scanf("%ld", &Case);

	while ( Case ){

		scanf("%ld", &Num);

		for (I = 0; I < Num; I++)
			scanf("%ld", &A[I]);

		Count = 0;
		for (I = 0; I < Num; I++){
			for (J = I+1; J < Num; J++){
				if (A [I] > A [J]){
					Temp = A [I];
					A [I] = A [J];
					A [J] = Temp;
					Count++;
				}
			}
		}
		printf("Optimal train swapping takes %ld swaps.\n", Count);

		Case--;
	}
	return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s