Помогите решить задачу python, ничего в голову не приходит
Алгоритм предназначен для сортировки массивов длиной n, состоящих из уникальных чисел в диапазоне от 0 до n-1. Иными словами, массив должен содержать целые положительные числа от 0 до n-1, перемешанные как угодно. Например, если n = 8, то массив может быть таким:
# Массив длиной 8 элементов
3 1 0 2 6 5 4 7 # В массиве содержатся все целые числа в диапазоне от 0 до 7.
Суть алгоритма: исходный массив разделяется на блоки так, чтобы каждый блок можно было отсортировать и при слиянии отсортированных блоков получился отсортированный массив. Менять блоки местами нельзя.
# Делим исходный массив на блоки, которые можно отсортировать:
# Так нельзя: после сортировки блоков их не объединить в отсортированный массив.
3 1 | 0 2 | 6 | 5 4 | 7
# И так нельзя.
3 | 1 0 2 | 6 5 4 7
3 1 0 2 | 6 5 4 | 7 # А вот такое деление - в самый раз!
# Сортируем блоки:
0 1 2 3 | 4 5 6 | 7
# Объединяем блоки:
0 1 2 3 4 5 6 7
# Получили отсортированный массив!
Алгоритм сортировки состоит из трёх шагов:
Разбить исходную последовательность на k блоков. Блоки могут иметь разные размеры. Первый блок обязательно должен содержать 0. Если длина первого блока — r элементов, то максимальным значением в первом блоке должно быть число r - 1. А следующий блок (если он вообще будет) должен содержать число r. Этот принцип должен соблюдаться и в последующих блоках.
Отсортировать каждый из блоков.
Объединить блоки в единый массив.
Такая сортировка выгодна в том случае, если разбить исходный массив на максимально возможное число блоков.
В этом задании вам предстоит реализовать только первый шаг: разбить массив на блоки и вернуть их количество.
Задание: написать программу, которая получает на вход массив и возвращает максимальное число блоков, на которое можно разбить этот массив так, чтобы сортировка отработала корректно.
Ещё один пример:
3 2 0 1 4 6 5
Минимальный размер первого блока — 4.
Если взять лишь первые два элемента, то отсортированная последовательность будет начинаться с двойки, а это неправильно. Если взять первые три элемента, то последовательность будет начинаться с нуля, но после него сразу же пойдёт двойка. Опять нехорошо.
А вот первые четыре элемента гарантируют, что первая часть результирующего массива будет корректной.
Четвёрку можно взять как отдельный блок из одного элемента.
Последние два элемента составят третий блок. Таким образом:
первый блок: 3, 2, 0, 1;
второй блок: 4;
третий блок: 6, 5.
В этом примере ответ равен 3: чтобы сортировка блоками отработала корректно, полученный массив можно разделить максимум на три блока.
Формат ввода
В первой строке задано n — количество чисел для сортировки (n ≤ 1000). В следующей строке записаны числа от 0 до n - 1, которые надо разбить на блоки.
Формат вывода
Выведите максимальное число блоков, на которое можно разбить данные при использовании метода частичной сортировки.
def max_blocks(arr):
n = len(arr)
max_block_count = 0 # Количество блоков
current_max = 0 # Максимальное значение в текущем блоке
for i in range(n):
current_max = max(current_max, arr[i])
# Если индекс достиг максимального значения в текущем блоке,
# это означает, что мы можем завершить блок здесь.
if current_max == i:
max_block_count += 1
current_max = 0 # Сброс для следующего блока, если он есть
return max_block_count
# Чтение ввода пользователя
n = int(input()) # количество чисел для сортировки
arr = list(map(int, input().split())) # числа для сортировки
# Вывод результата
print(max_blocks(arr)) Обходите массив, контрольное число первое, пока очередное число меньше первого - игнор, все в блок, как только больше, счетчик + 1, контрольное число становится очередным - начало нового блока
Изи