удалить некоторые элементы массива

113

03 ноября 2021, 07:30

Например, у меня есть массив [5, 3, 6, 1, 4, 2]. Требуется удалить некоторые элементы до того, что массив должен отсортироваться. Требуется сделать это за минимальное количество ходов

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 100 000) — количество чисел

Во второй строке записаны n целых чисел p[i] (1 ≤ p[i] ≤ n, p[i] ≠ p[j] при i ≠ j) — последовательность чисел.

Выходные данные

Выведите целое число — минимальное количество действий, необходимое для сортировки массива

Answer 1

Переформулируем задачу. Нужно найти максимальную возрастающую последовательность. Почему это так - думаю понятно. Именно она останется неудалённой.

Методов для решения есть глобально 2. Это бинарный поиск с динамикой. Или дерево. Напишу сначала тривиальное решение за квадрат.

// fill F - array 1
for (int i=0; i<n; ++i) 
    for (int j=0; j<i; ++j)
        if (a[j] <= a[i])
            F[i] = max (F[i], F[j] + 1);

Теперь есть 2 варианта ускорения. Или используем структуру чтобы убрать 2 цикл и заменить на поиск максимума в дереве отрезков. Или используем бинарный поиск (последнее не очевидно).

В общем вот ссылка дальше сами. http://e-maxx.ru/algo/longest_increasing_subseq_log

P.S. я предполагаю что отсортировать надо по возрастанию. Если нет - сделайте тоже самое только в обратную сторону и найдите лучший результат.