Найти минимальные суммарные энергозатраты для сортировки чисел вставками, при этом выполняя вставку с использованием наименьшего количества энергии

Условие:

Решить

Решение:

### Предмет: Информатика / Программирование ### Раздел: Алгоритмы и структуры данных, сортировка вставками ### Задача: Нам нужно найти минимальные суммарные энергозатраты для сортировки чисел вставками, при этом выполняя вставку с использованием наименьшего количества энергии. Из-за вставки чисел с одного края или другого, могут быть различные энергозатраты, и нужно найти оптимальный способ вставки. ### Пояснение: Необходимо каждый раз выбирать такой край последовательности, куда вставлять элемент, чтобы минимизировать количество пересортировок (энергозатрат) при вставке. ### Решение: 1. **Алгоритм сортировки вставками**: - Иннокентий выбирает число и вставляет его либо слева, либо справа от текущей отсортированной последовательности. - Энергозатраты равны количеству перестановок, необходимых для переноса числа в нужную позицию. - Эти энергозатраты зависят от того, с какого конца (слева или справа) мы будем вставлять число. 2. **Описание плана**: - Мы итеративно вставляем число по одному. Для каждого числа проверяем, выгоднее вставить его слева или справа (по энергозатратам). - Для определения энергозатрат нужно посчитать минимальное количество шагов и суммировать его для каждого вставляемого элемента. 3. **План действий**: - В начале отсортированный массив пустой. Мы начинаем добавлять числа одно за другим, проверяя, с какой стороны будет меньше энергозатрат на вставку. 4. **Алгоритм**: Нам необходимо симулировать процесс вставки для каждого элемента либо в начало, либо в конец отсортированного массива. В зависимости от того, сколько элементов нужно будет сдвинуть, вычисляем текущие энергозатраты и выбираем минимальные. ### Решение на Python: ```python def solve(): n = int(input()) # Читаем длину перестановки a = list(map(int, input().split())) # Читаем саму перестановку result = 0 # Итоговые минимальные энергозатраты sorted_part = [] # Будем постепенно строить отсортированную часть for elem in a: # Вставляем элемент в начало или в конец уже отсортированной части left_cost = 0 if not sorted_part else sorted_part[0] - elem right_cost = 0 if not sorted_part else elem - sorted_part[-1] if left_cost <= right_cost: sorted_part.insert(0, elem) # вставляем слева result += len(sorted_part) else: sorted_part.append