Найти общую стоимость удаления максимального числа по одному из массива

Question

Мне дана последовательность из n различных целых чисел a0, a1, ... a (n − 1). В каждой итерации я выбираю максимальное число и удаляю его; стоимость удаления максимального числа - это число чисел слева от него. Повторите это n раз. Я должен найти общую стоимость n итераций.

Например, если A [] = {6, 2, 8, 4, 9, 3}
Общая стоимость: 4 + 2 + 0 + 1 + 1 + 0 = 8

Я знаю, что есть O (n logn) алгоритмы для решения этой проблемы, распространенными из которых являются подход сортировки слиянием и подход BST.

Но я я запутался в том, как реализовать подход BST. Любая помощь в том, как начать, будет любезно оценен.

Answer 1

Но я не совсем понимаю, как реализовать подход BST.

Если вы пишете сбалансированное двоичное дерево поиска (например, красно-черное дерево) реализация), и он будет отслеживать размер поддерева каждого узла (что вы можете сделать, не затрагивая асимптотику c гарантии сложности), тогда вы можете дать ему "index of" или "count меньше чем" метод, который вычисляет за O (log n), сколько элементов меньше заданного значения.

Создание этой реализации - сложная часть (хотя, по крайней мере, вам не нужно поддерживать удаление); как только он у вас есть, алгоритм довольно прост:

• инициализирует дерево, изначально пустое
• инициализирует целое число результат , изначально ноль
• для каждого элемента elem :
  • спросите дерево, сколько элементов меньше elem ; добавить это число к результат
  • добавить элемент к дереву
• возврат результат

Answer 2

TLDR:
Вы ищете количество инверсий в массиве для сортировки по убыванию. Это выполнимо в O(n lg n).

. Число инверсий в массиве A определяется как число всех пар индексов i, j, таких как i < j и * 1009. *. Таким образом, в основном количество пар значений в A, такое, что первое будет появляться после второго, если будет A отсортировано. Это можно рассчитать, пройдя все значения в A и посчитав предшествующие значения, которые должны прийти после:

count_inversions(A):
    count = 0
    for i=0 to length of A - 1:
        for j=0 to i - 1:
            if A[i] > A[j]:
                count++
    return count

Для вашей задачи наивное решение будет очень похоже:

total_delete_cost(A):
    count = 0
    for i=0 to length of A - 1:
        for j=0 to i - 1:
            if A[i] < A[j]:
                count++
    return count

Единственное, что изменилось, это строка if A[i] > A[j]. Или с другой стороны: каждое значение x в A добавит m к общей стоимости, где m - это число значений, которые больше x и имеют более высокий индекс. Это точно количество инверсий для обратного порядка от A.

С этого момента на оставшуюся часть вопроса дается ответ здесь , за исключением незначительной адаптации для перехода от возрастания к убыванию, поэтому я не буду публиковать код для решения оставшейся части проблема.