Решение задачи #26. Python Яндекс CodeRun, Машинки

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Машинки.
Сложность: Сложная.
Статус решения: "Решено".

Условие задачи:
Петя, которому три года, очень любит играть с машинками. Всего у Пети N различных машинок, которые хранятся на полке шкафа так высоко, что он сам не может до них дотянуться. Одновременно на полу комнаты может находиться не более K машинок. Петя играет с одной из машинок на полу и если он хочет поиграть с другой машинкой, которая также находится на полу, то дотягивается до нее сам. Если же машинка находится на полке, то он обращается за помощью к маме. Мама может достать для Пети машинку с полки и одновременно с этим поставить на полку любую машинку с пола. Мама очень хорошо знает своего ребенка и может предугадать последовательность, в которой Петя захочет играть с машинками. При этом, чтобы не мешать Петиной игре, она хочет совершить как можно меньше операций по подъему машинки с пола, каждый раз правильно выбирая машинку, которую следует убрать на полку. Ваша задача состоит в том, чтобы определить минимальное количество операций. Перед тем, как Петя начал играть, все машинки стоят на полке.

Формат ввода (input):
В первой строке содержаться три числа N, K и P (1≤K≤N≤1000001≤K≤N≤100000, 1≤P≤5000001≤P≤500000). В следующих P строках записаны номера машинок в том порядке, в котором Петя захочет играть с ними.

Формат вывода (Output):
Выведите единственное число: минимальное количество операций, которое надо совершить Петиной маме.

Решение:

Python

import sys
import heapq
from collections import defaultdict, deque

def main():
    """Функция main решает задачу минимизации операций для доставания машинок с полки."""

    # Считываем входные данные
    input_lines = sys.stdin.read().splitlines()
    N, K, P = map(int, input_lines[0].split())  # Количество машинок (N), максимальное количество на полу (K), запросов (P)

    # Преобразуем последовательность запросов в список
    requests = [int(x) for x in input_lines[1:P + 1]]

    # Создаем словарь для хранения очередей индексов запросов для каждой машинки
    next_use = defaultdict(deque)
    for idx, request in enumerate(requests):
        next_use[request].append(idx)

    # Создаем множество для хранения машинок, которые находятся на полу
    on_floor = set()

    # Создаем кучу для хранения кортежей (время следующего использования, машинка)
    heap = []

    # Переменная для подсчета количества операций
    operations = 0

    # Обрабатываем каждый запрос
    for idx, request in enumerate(requests):
        # Обновляем очередь следующего использования для текущей машинки
        if next_use[request]:
            next_use[request].popleft()

        if request not in on_floor:  # Если нужная машинка не на полу
            operations += 1  # Увеличиваем счетчик операций

            if len(on_floor) == K:  # Если на полу уже находится максимум машинок
                # Удаляем машинку, которая будет использована позже всех
                _, farthest_car = heapq.heappop(heap)
                on_floor.remove(farthest_car)

            # Добавляем текущую машинку на пол
            on_floor.add(request)

        # Обновляем кучу для текущей машинки
        if next_use[request]:
            heapq.heappush(heap, (-next_use[request][0], request))  # Используем отрицательное время для max-heap
        else:
            heapq.heappush(heap, (-float('inf'), request))  # Если машинка больше не понадобится

    # Выводим результат
    print(operations)

# Запускаем функцию main
if __name__ == "__main__":
    main()

Объяснение кода

Код решает задачу минимизации количества операций для доставания машинок с полки, используя алгоритм с приоритетной очередью (кучей).

1. Считывание входных данных :
   • N — общее количество различных машинок.
   • K — максимальное количество машинок, которые можно хранить на полу одновременно.
   • P — количество запросов.
   • Запросы представляют собой последовательность чисел, где каждое число — это индекс машинки, которую нужно достать.
2. Подготовка данных :
   • Создается словарь next_use, где для каждой машинки хранится очередь (с помощью deque) индексов её использования в будущем.
   • Например, если машинка 3 используется на позициях 5 и 10, то next_use[3] = deque([5, 10]).
3. Инициализация структур данных :
   • on_floor — множество текущих машинок, находящихся на полу.
   • heap — куча, где хранятся кортежи (время следующего использования, индекс машинки). Используется для отслеживания, какая машинка будет использована позже всех.
   • operations — счетчик операций (сколько раз пришлось доставать машинку с полки).
4. Обработка каждого запроса:
   • Для каждой машинки из запросов:
     • Удаляется текущий индекс использования из очереди next_use.
     • Если машинка уже на полу (request in on_floor), ничего не делаем.
     • Если машинки нет на полу:
       • Увеличиваем счетчик операций (operations += 1).
       • Если на полу уже находится максимальное количество машинок (len(on_floor) == K):
         • Удаляем машинку, которая будет использована позже всех. Это делается с помощью heapq.heappop(heap), который извлекает машинку с максимальным временем следующего использования (благодаря отрицательному значению времени).
       • Добавляем текущую машинку на пол (on_floor.add(request)).
     • Обновляем кучу:
       • Если машинка еще понадобится, добавляем её в кучу с временем следующего использования.
       • Если машинка больше не понадобится, добавляем её в кучу с бесконечным временем (-float('inf')).
5. Вывод результата:
   • После обработки всех запросов выводится значение operations — минимальное количество операций.

Источник решения: hdhai.com