88
правок
Изменения
Нет описания правки
''//сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1 - ую, которой еще нет в нашем префиксе, пусть это цифра j''
ans[i] = j (посчитаем за <tex>O(n) </tex>)
теперь j-ый элемент занят(находится в нашем префиксе)
Данный алгоритм работает за <tex>O(n^2) </tex>. Мы можем посчитать все <tex>P_{n} </tex> за <tex>O(n) </tex>. Асимптотику можно улучшить
