Example Input

3
3
1 3 2
4
4 3 2 1
2
2 1

Example Output

Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.


解法:問你氣泡(Bubble Sort)排序的次數


import java.util.Scanner;

public class UVA299 {

 public static void main(String[] args) {

  Scanner sc = new Scanner(System.in);

  int volume = sc.nextInt();

  for (int i = 0; i < volume; i++) {

   int count = 0;

   int num_c = sc.nextInt();

   int matrix[] = new int[num_c];

   for (int j = 0; j < num_c; j++) {

    matrix[j] = sc.nextInt();

   }

   for (int k = 0; k < matrix.length; k++) {

    for (int j = k + 1; j < matrix.length; j++) {

     if (matrix[k] > matrix[j])

     {

      swap(matrix[k], matrix[j]);

      count++;

     }

    }

   }

   System.out.println("Optimal train swapping takes " + count
     + " swaps.");
  }

  sc.close();
 }

 private static void swap(int i, int j) {

  int temp = 0;

  temp = i;
  i = j;
  j = temp;

 }

}