Крайний Банк

Пусть мы знаем все пары покупка-продажа, как трейдер дошел до состояния, описанного во входных данных. Заметим, что если есть пара вида $$$(i, j)$$$ и в момент $$$j$$$ у нас была какая-то незакрытая сделка, в которой стоимость покупки больше чем $$$a_i$$$, но при этом меньше $$$a_j$$$, то мы можем поменять моменты покупки в этих парах и всё останется корректным.

Из этого замечания сразу же следует жадный алгоритм для решения задачи. Давайте идти по моментам времени и если мы находимся в моменте где трейдер продавал, то будем ставить ему в пару максимальный незанятый момент покупки, стоимость товара в котором не превышает текущей стоимости продажи. Таким образом мы либо получим корректное разбиение на пары, либо в какой-то момент столкнемся с противоречием (не будет подходящего момента покупки), что значит, что трейдер никак не мог исполнить условие, для того, чтобы быть потенциальным мошенником.

Для эффективной реализации данного решения предлагается для каждого значения $$$a_i$$$ массив с ещё не занятыми моментами покупки, имеющими такую стоимость. Если нам встретится момент продажи, то нам нужно будет найти максимальный, по стоимости, не занятый момент покупки, не превышающий данного $$$a_i$$$. Это легко можно сделать используя массивы, который мы поддерживаем (достаточно пройтись от $$$a_i - 1$$$ до $$$1$$$ и найти первый непустой массив). После этого мы создаем пару с любым элементом из этого массива и данным индексом. Удаляем данный индекс из этого массива и продолжаем процесс. Заметим, что для эффективной реализации следует всегда брать в пару последний элемент из массива, так как его удаление будет работать за $$$O(1)$$$. Таким образом мы получаем решение за $$$O(n)$$$.