1

我正在尝试解决问题 #299 - 在网站 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.

我的代码打印到第二个解决方案，然后由于某种原因停止。我试图调试它并一步一步检查发生了什么，但它让我到了偏头痛的地步。任何见解都受到高度赞赏。

...更准确地说，它第三次在第二个for循环处停止，没有将任何东西放入数组中......我不知道为什么！

我发现的另一件事是，要解决这个问题，中间情况的交换次数是 6，因此冒泡排序在这里不会有用，因为它进行超过 10 次交换，从而产生错误的输出，这是一个单独的问题但是，对于我提出的原始版本。我仍然没有弄清楚为什么它会在我第三次为数组赋值的循环中第三次停止。

4

1 回答 1

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.");
        }
    }
}
于 2013-10-05T04:48:37.730 回答