Ошибка Java Judge Solution Solution

Question

Я пытаюсь решить проблему # 299 - Поезд Swapping на сайте UVa Online судья. Код, который у меня работает, отлично подходит для независимых тестовых случаев. Однако, когда я использую входной выборки они предоставляют, моя программа пропускает один из тестов, последний из которых более конкретно:

Вот мой код:

import java.util.Scanner; 
public class Tester { 
    void problem(){ 
    Scanner imput = new Scanner(System.in); 
    int numT =imput.nextInt(); 
    int numL, aux, swaps=0; 
    int [] train = new int [50]; 

    for (int i =0; i<numT; i++) { 
     numL = imput.nextInt(); 

     for (int m =0; m< numL; m++) { 
     train[m]=imput.nextInt(); 
     } 

     for (int j=0; j<numL; j++) { 
     if (train[j]>train[j+1]) { 
      for (int k =j; k<numL-1;k++) { 
      aux = train[k]; 
      train[k]=train[k+1]; 
      train[k+1]=aux; 
      swaps++; 
      } 
     } 
     } 
     System.out.println("Optimal train swapping takes "+swaps+" swaps."); 
     swaps = 0; 
    } 
    } 
} 

Пример ввода:

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

Результат:

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

мой код печатает до второго раствора, то для S ome причина останавливается. Я попытался отладить его и проверить, что происходит шаг за шагом, но это привело меня к точке мигрени. Любое понимание высоко ценится.

... Чтобы быть более точным он останавливается на втором для цикла в третий раз вокруг, не принимая ничего в массив ... и я не знаю, почему!

Еще одна вещь, которую я выяснил, заключается в том, что для решения этой проблемы количество свопов для случая середины равно 6, поэтому сортировка пузырьков здесь не будет полезной, поскольку она делает более 10 своп, что дает неправильный вывод, это это отдельный вопрос к оригиналу, который я представил. Я все еще не понимаю, почему он останавливается в третий раз вокруг цикла, где я назначаю значения массиву в третий раз.

Answer 1

Перестановка свой цикл, как следующим образом:

for(int j=0; j<numL; j++){ 
for(int k =j+1; k<numL;k++){ 
    if(train[j]>train[k]){ 
      aux = train[j]; 
      train[j]=train[k]; 
      train[k]=aux; 
      swaps++; 
     } 
    } 
} 

Отредактировано: для повышения производительности.

Вы можете свести к минимуму для цикла, если вы организуете свой код, как показано ниже:

public class Main { 
    static int sum=0; 
    public static void sort(String[] str){ 
     for(int i = 1; i < str.length; i++) 
      if(Integer.parseInt(str[i])<Integer.parseInt(str[i-1])){ 
       String h = str[i]; 
       str[i] = str[i-1]; 
       str[i-1] = h; 
       sum++; 
       sort(str); 
      } 
    } 
    public static void main(String[] args) throws NumberFormatException, IOException { 
     BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); 
     int n = Integer.parseInt(in.readLine().trim()); 
     for (int i = 0; i < n; i++) { 
      sum = 0; 
      int x = Integer.parseInt(in.readLine().trim()); 
      String s[] = in.readLine().trim().split(" +"); 
      sort(s); 
      System.out.println("Optimal train swapping takes " + sum + " swaps."); 
     } 
    } 
}