Как подойти к проблемам BST?

Question

Мне дали эту задачу:

Вам дана последовательность из n различных целых чисел a0, a1,. , , ан-1. В каждой итерации вы выбираете максимальное число и удаляете его, стоимость определения максимального числа - это число чисел слева от него. Повторите это n раз. Учитывая, что ai реализует алгоритм O (n log n) для вычисления общей стоимости n итераций.

Я знаю, что мы должны использовать BST для решения этой проблемы, так как это O (N log N ), однако, я не уверен, что делать.

Я думал, что смогу хранить значения и индексы в hashMap, и когда удаление будет выполнено, мы ищем этот индекс в BST и добавляем значения индекса в пройденный путь. Однако, удаляя узел, мы должны уменьшить значения индекса BST для всех индексов> того, который будет удален.

Я не уверен, возможно ли это, и я хотел бы получить любой совет / руководство по этому вопросу:)

Answer 1

Хотя @ 0x499602D2 комментарий правильный, сортировка - верный путь к go. Эта проблема - еще одно применение сортировки слиянием, похожее на подсчет инверсии.

Слияние элемента справа уменьшает стоимость на количество элементов, оставшихся слева (понимаете почему?). После полной сортировки массива стоимость снижается до 0.

Надеюсь, этого достаточно, чтобы начать работу.