Это вопрос домашнего задания, о котором я много размышлял.
Предположим, у меня есть несортированный массив целых чисел и заданное целое число d.Задача состоит в том, чтобы подсчитать количество инверсий, которое включает перестановки, превышающие d.
Например, при заданном входном массиве (3, 4, 3, 1) и d = 2 количество таких инверсий равно 1так как учитывается только инверсия между 4 и 1.Другие инверсии имеют разницу менее 2.
Конечно, простой способ подсчета количества инверсий состоит в том, чтобы выполнять итерации по каждому номеру списка и добавлять число элементов перед этим числом,который меньше, а разница больше, чем d.Однако это алгоритм ^ 2.Вместо этого необходим алгоритм n \ log n.
Здесь представлен еще один более эффективный алгоритм, в котором мы выполняем сортировку слиянием для входного массива и отсчитываем напрямую.https://www.geeksforgeeks.org/counting-inversions-subarrays-given-size/
Однако у меня возникли проблемы с изменением этого, чтобы получить правильный ответ.
Мой подход выглядит примерно так:
На этапе слияния 'merge', если первый элемент левого подмассива меньше, просто добавьте его в отсортированный массив и продолжайте.
Иначе, я увеличиваю количество необходимых инверсий с количеством элементов в левом подмассиве больше, чем у первого элемента правого подмассива на d.
Тем не менее, у меня все еще проблемыполучить правильный ответ.
Может кто-нибудь, пожалуйста, помогите мне?Спасибо.