Codeforces Round 982 (Div. 2) |
---|
Закончено |
Сталинская сортировка — это юмористический алгоритм сортировки. Вместо траты сил на сортировку элементов должным образом, элементы на неправильных позициях просто удаляются. Сложность алгоритма — $$$\mathcal{O}(n)$$$.
Алгоритм устроен следующим образом: начиная со второго элемента массива, если текущий элемент строго меньше предыдущего элемента (игнорируя те, которые уже были удалены), то удалите текущий элемент. Продолжайте проход по массиву до тех пор, пока он не будет отсортирован по неубыванию. Например, массив $$$[1, 4, 2, 3, 6, 5, 5, 7, 7]$$$ превращается в $$$[1, 4, 6, 7, 7]$$$ после сталинской сортировки.
Назовём массив уязвимым, если вы можете отсортировать его в невозрастающем порядке, применив сталинскую сортировку к любым его подотрезкам$$$^{\text{∗}}$$$ столько угодно раз.
Для массива $$$a$$$, состоящего из $$$n$$$ целых чисел, определите минимальное количество элементов, которое нужно удалить из массива, чтобы он стал уязвимым.
$$$^{\text{∗}}$$$Массив $$$a$$$ является подмассивом $$$b$$$, если $$$a$$$ может быть получен из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2000$$$) — длина массива.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$.
Для каждого набора входных данных выведите одно целое число — минимальное количество элементов, которое нужно удалить из массива, чтобы он стал уязвимым.
673 6 4 9 2 5 255 4 4 2 282 2 4 4 6 6 10 101100096 8 9 10 12 9 7 5 47300000000 600000000 400000000 900000000 200000000 400000000 200000000
2 0 6 0 4 2
В первом наборе входных данных оптимально будет удалить числа $$$3$$$ и $$$9$$$. Тогда у нас останется $$$a = [6, 4, 2, 5, 2]$$$. Чтобы показать, что этот массив уязвим, мы можем сначала применить сталинскую сортировку к подмассиву $$$[4, 2, 5]$$$, чтобы получить $$$a = [6, 4, 5, 2]$$$, а затем применить сталинскую сортировку к подмассиву $$$[6, 4, 5]$$$, чтобы получить массив $$$a = [6, 2]$$$, который является невозрастающим.
Во втором наборе входных данных массив уже является невозрастающим, поэтому нам не нужно удалять элементы.
Название |
---|