Задача в том, что бы вывести максимальное число блоков, на которое можно разбить данные при использовании метода частичной сортировки
Я выявил закономерность, что нужно срезать массив от начала входных данных и до нуля, если этот массив сортируется так, что каждый символ равен своему индексу, то это один блок, если нет то рекурсивным вызовом берем срез от начала и до числа 0 и плюс еще один правый символ, и так, пока каждый символ не будет равен своему индексу, но получилось так, что даже когда символ равен своему индексу, это условие if после которого должна была функция вернуть число, но нет, все равно срабатывет else и рекурсия продолжается, хотя так же не должно быть. Пробовал на входных данных 3 6 7 4 1 5 0 2, ответ должен быть 1
cc = input().split()
ccc = [int(i) for i in cc]
index_nul = ccc.index(0)
def block(index_nu):
spis_nul = ccc[:index_nu + 1]
sort_spis_nul = sorted(spis_nul)
count = 0
len_spis = len(sort_spis_nul)
for i in sort_spis_nul:
if i == sort_spis_nul.index(i):
count += 1
if count == len_spis:
return 1
else:
block(index_nu + 1)
print(block(index_nul))
Задача с яндекс.контест сортировка слиянием блоков.
Условие задачи:
Задание: написать программу, которая получает на вход массив и возвращает максимальное число блоков, на которое можно разбить этот массив так, чтобы сортировка отработала корректно.
Ещё один пример:
3 2 0 1 4 6 5 Минимальный размер первого блока — 4.
Если взять лишь первые два элемента, то отсортированная последовательность будет начинаться с двойки, а это неправильно. Если взять первые три элемента, то последовательность будет начинаться с нуля, но после него сразу же пойдёт двойка. Опять нехорошо.
А вот первые четыре элемента гарантируют, что первая часть результирующего массива будет корректной.
Четвёрку можно взять как отдельный блок из одного элемента.
Последние два элемента составят третий блок. Таким образом:
первый блок: 3, 2, 0, 1; второй блок: 4; третий блок: 6, 5. В этом примере ответ равен 3: чтобы сортировка блоками отработала корректно, полученный массив можно разделить максимум на три блока.