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

Предмет: Информатика / Программирование

Раздел: Алгоритмы и структуры данных, сортировка вставками

Задача:

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

Пояснение:

Необходимо каждый раз выбирать такой край последовательности, куда вставлять элемент, чтобы минимизировать количество пересортировок (энергозатрат) при вставке.

Решение:

1. Алгоритм сортировки вставками:
   • Иннокентий выбирает число и вставляет его либо слева, либо справа от текущей отсортированной последовательности.
   • Энергозатраты равны количеству перестановок, необходимых для переноса числа в нужную позицию.
   • Эти энергозатраты зависят от того, с какого конца (слева или справа) мы будем вставлять число.
2. Описание плана:
   • Мы итеративно вставляем число по одному. Для каждого числа проверяем, выгоднее вставить его слева или справа (по энергозатратам).
   • Для определения энергозатрат нужно посчитать минимальное количество шагов и суммировать его для каждого вставляемого элемента.
3. План действий:
   • В начале отсортированный массив пустой. Мы начинаем добавлять числа одно за другим, проверяя, с какой стороны будет меньше энергозатрат на вставку.
4. Алгоритм:

   Нам необходимо симулировать процесс вставки для каждого элемента либо в начало, либо в конец отсортированного массива. В зависимости от того, сколько элементов нужно будет сдвинуть, вычисляем текущие энергозатраты и выбираем минимальные.

Решение на 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 += left_cost
        else:
            sorted_part.append(elem)
            result += right_cost
    print(result)