Произвольная перестановка и подсчет количества позиций a [i] <a [i + 1] в перестановке

Question

Первая строка содержит количество марафонов t < 100.Каждый марафон указан тремя строчками.Первая строка содержит количество бегунов 1 < n <= 40000.Вторая строка - это перестановка начальных чисел 1,...,n, которая представляет порядок, в котором бегуны прошли начальную линию.Наконец, третья строка - это перестановка, которая представляет конечный порядок.Для каждого марафона выведите одну строку, которая содержит минимальное количество обгонов, которые произошли во время гонки.

Так, например,

Я действительно не знаю, как я могу создать случайную перестановку 1 < n и как найтиЗатем, сколько обгонов произошло.Для последнего я бы проверил, сколько чисел больше следующего, то есть, если 4 > 3, тогда я увеличу int overtaking++;

import java.util.Scanner;

public class MarathonMovement {

   public static void main(String[] args) {

       Scanner NoM = new Scanner(System.in); // Number of marathons
       int t = NoM.nextInt();

       Scanner NoR = new Scanner(System.in); // First line: Number of runners
       int n = NoR.nextInt();

       // Second line: Permutation of starting numbers representing the order in which the runners passed the starting line

       // Third line: Permutation which represents finishing order

        int overtakings = 0;

        for (int i = 0; i < n; i++){
           if {
               // logic
               overtakings++;
           }
        }

       for(int x = 0; x < t; x++){
          System.out.println("at least" + overtakings + " overtaking(s)");
       }
   }
}

Answer 1

Для первой части вашего вопроса (сгенерируйте случайную перестановку) вы можете использовать метод Collections.shuffle:

    List<Integer> start = new ArrayList<>();
    for (int i = 0; i < n; ++i) {
        start.add(i + 1);
    }
    List<Integer> finish = new ArrayList<>(start);
    Collections.shuffle(finish);

Для подсчета обгонов:

    int overtakings = 0;
    for (int i = 1; i < n; ++i) {
        if (finish.get(i) < finish.get(i-1)) {
            ++overtakings;
        }
    }

Answer 2

Если я правильно понимаю эту задачу, то это мое решение:

public static void main(String... args) {
    try (Scanner scan = new Scanner(System.in)) {
        int t = scan.nextInt();

        for (int i = 0; i < t; i++) {
            int n = scan.nextInt();
            int[] arr = new int[n];
            Set<String> uniqueOvertaking = new HashSet<>();

            for (int j = 0; j < n; j++)
                arr[j] = scan.nextInt();
            for (int j = 0; j < n; j++) {
                int val = scan.nextInt();

                if (arr[j] != val)
                    uniqueOvertaking.add(Math.min(arr[j], val) + "->" + Math.max(arr[j], val));
            }

            int res = uniqueOvertaking.size() == n ? uniqueOvertaking.size() - 1 : uniqueOvertaking.size();
            System.out.println("at least " + res + " overtaking(s)");
        }
    }
}

Выход:

at least 1 overtaking(s)
at least 5 overtaking(s)
at least 3 overtaking(s)