Stepik - 6.4. Число инверсий в массиве
Описание задачи
Первая строка содержит число 1≤n≤10^5, вторая — массив A[1…n], содержащий натуральные числа, не превосходящие 10^9. Необходимо посчитать число пар индексов 1≤i<j≤n, для которых A[i]>A[j]. (Такая пара элементов называется инверсией массива. Количество инверсий в массиве является в некотором смысле его мерой неупорядоченности: например, в упорядоченном по неубыванию массиве инверсий нет вообще, а в массиве, упорядоченном по убыванию, инверсию образуют каждые два элемента.)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
/**
* Main
*
* @author Vladislav Sidlyarevich <vlsidlyarevich@gmail.com>
* Created on 5/16/21.
*/
public class Main {
long inversions = 0;
public static void main(String[] args) {
Main main = new Main();
main.run();
}
public void run() {
Scanner scanner = new Scanner(System.in).useDelimiter("\n");
scanner.nextLine();
List<Integer> input = Arrays.stream(scanner.nextLine().split("\\s+"))
.map(Integer::parseInt)
.collect(Collectors.toList());
sort(input);
System.out.println(inversions);
}
private List<Integer> sort(final List<Integer> input) {
if(input.size() == 1) return input;
int median = input.size() / 2;
List<Integer> left = input.subList(0, median);
List<Integer> right = input.subList(median, input.size());
return merge(sort(left), sort(right));
}
private List<Integer> merge(List<Integer> left, List<Integer> right) {
List<Integer> mergeResult = new ArrayList<>();
int l = 0, r = 0;
while (l < left.size() && r < right.size()) {
if (left.get(l) <= right.get(r)) {
mergeResult.add(left.get(l));
l++;
} else {
mergeResult.add(right.get(r));
r++;
inversions += left.size() - l;
}
}
//Add last elements in one batch
if (l < left.size()) {
mergeResult.addAll(left.subList(l, left.size()));
} else if (r < right.size()) {
mergeResult.addAll(right.subList(r, right.size()));
}
return mergeResult;
}
}