uva/UVa00299_TrainSwapping.java at master · improper4/uva · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package uva;
/* USER: 46724 (sfmunera) */
/* PROBLEM: 235 (299 - Train Swapping) */
/* SUBMISSION: 08575796 */
/* SUBMISSION TIME: 2011-02-13 19:05:06 */
/* LANGUAGE: 2 */

import java.util.*;

public class UVa00299_TrainSwapping {

    public static void main(String[] args) {

        try {
            Scanner in = new Scanner(System.in);

            int N = in.nextInt();
            for (int i = 0; i < N; ++i) {
                int L = in.nextInt();
                int[] wagons = new int[L];

                for (int j = 0; j < L; ++j)
                    wagons[j] = in.nextInt();

                int swaps = 0;
                int cur = 1;
                while (cur <= L) {
                    int ind = 0;

                    for (int k = 0; k < L; ++k)
                        if (wagons[k] == cur) {
                            ind = k;
                            break;
                        }
                    if (ind < cur - 1) {
                        for (int k = ind; k < cur - 1; ++k) {
                            int tmp = wagons[k];
                            wagons[k] = wagons[k + 1];
                            wagons[k + 1] = tmp;
                            ++swaps;
                        }
                    } else if (ind > cur - 1) {
                        for (int k = ind; k > cur - 1; --k) {
                            int tmp = wagons[k];
                            wagons[k] = wagons[k - 1];
                            wagons[k - 1] = tmp;
                            ++swaps;
                        }
                    }
                    ++cur;
                }
                System.out.println("Optimal train swapping takes " + swaps + " swaps.");
            }
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(0);
        }
    }
}