Переход к следующему ближайшему элементу

Question

Для массива из N элементов, пронумерованных от 1 до N. i-й элемент имеет значение V [i]. Также все элементы различны.

Чтобы перейти от i-го элемента к i-му элементу, нам нужно потратить стоимость | i-j |. Но мы можем перейти от Ith до -м элемента только если:

1. J не ближе, чем позиции K от ключа я (т.е. J не должно быть в диапазоне [I-K + 1, я + K- 1]).

2. V [j] < V [i].

Каждый элемент может иметь 0 или более элементов, к которым можно подпрыгнуть.

Нам нужно найти суммирование затрат, необходимых для перехода от каждого элемента i к ближайшему элементу, который можно подскочить после него. Если нет следующего элемента, к которому мы можем перейти для элемента i, тогда рассмотрим его стоимость как 0.

Пример: Пусть N = 5 и K = 1, а массив - [3,5,4,2,1 ], то здесь ответ 6

Объяснение:

The next jumping elements for: 
1 is { }. Closest=none, so cost = 0 
2 is { 1 }. Closest=1, so cost = 1 
3 is { 1 , 2 }. Closest=2, so cost = 3 
4 is { 1 , 2 , 3 }. Closest=2, so cost= 1 
5 is { 1 , 2 , 3 , 4 }. Closest=3 or 4, so cost = 1 

Общая стоимость 6

Я знаю грубую решение, которое будет работать в O (N^2). Но 1 < = N < = 2 * 10^5 и 1 < = K, V [i] < = N. Так что может быть лучшим способом решить эту проблему?

Answer 1

Используя двоичное дерево для хранения индексов, вы можете уменьшить его от O (n^2) до O (n^lg (n)).

Начать с пустого дерева T, перебирать из 1 -> N. На каждом шаге, когда вы вводите новый индекс в дереве, вы также можете получить самый близкий индекс.