Java在線裁判解決方案錯誤

Question

我想解決問題＃299 - 在網站UVa在線裁判列車交換。我的代碼對於獨立測試用例工作正常。然而，當我使用他們提供的樣品輸入，我的程序省略的測試情形之一的，最後一個更加具體：

這裏是我的代碼：

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++; 
     } 
    } 
} 

編輯：性能。

您可以最小化for循環，如果你組織類似下面的代碼：

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."); 
     } 
    } 
}