e-olimp: 694. Минимум в очереди

e-olimp: 694 — Минимум в очереди

Постановка задачи

На вход программы подается набор операций с очередью. Каждая операция состоит в добавлении или удаления элемента из очереди. После выполнения каждой операции найдите наименьшее число, которое находится в очереди. Сложите все полученные числа и получите ответ. Если после некоторой операции очередь оказалась пуста, то ничего не прибавляйте к ответу. Если выполнить удаление невозможно, так как очередь пуста, то не выполняйте его.

Алгоритм решения

Классическая модификация очереди с поддержкой минимального хранимого значения подразумевает использование двух модифицированных стеков, один из которых служит только для проталкивания элементов в очередь, а другой — только для выталкивания. Стеки хранят пары значений: непосредственно элемент и минимальное значение в очереди на момент его добавления, что позволяет поддерживать актуальную информацию при выполнении модифицирующих запросов (см. классический труд Кормена и статью на e-maxx). Более подробно механика процесса описана в комментариях к коду.

Реализации:

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

Спортивный подход

ideone: http://ideone.com/pvVixS
засчитанное решение: http://www.e-olimp.com/solutions/1926658

Преимущества

  • Простота. Концепция воплощается буквально — даже в условиях ограниченности во времени ошибиться трудно.
  • Наглядность и компактность кода.
  • Сообразность средств цели: постановка задачи требует реализации только трех функций: проталкивания, выталкивания и взятия крайнего элемента. Каждая из них реализована по возможности наиболее простым способом.

Недостатки

  • Немасштабируемость. При необходимости внедрения дополнительного функционала или изменении постановки задачи (скажем, отсутствии явной верхней границы для входных данных) возникают проблемы, решение которых неизбежно приводит к использованию объектно-ориентированных средств языка.
  • Перерасход памяти. Реальное количество одновременно содержащихся элементов в каждом из стеков на порядок меньше, но из формулировки задания это не следует и выясняется экспериментальным путём.
  • Костыли, избыточные сущности. Отличительная черта одноразового кода. Во время соревнования требования к коду достаточно мягкие: он должен работать. Желательно — предсказуемым образом. Причем, нередко реализуется не оптимальное и логичное решение, а то, которое понимаешь. Отладка и чтение таких программ — занятие не из приятных.

Объектно-ориентированный подход

ideone: http://ideone.com/A6BpwN
засчитанное решение: http://www.e-olimp.com/solutions/1924823

Преимущества

  • Масштабируемость. Добавление функционала сводится к написанию новых методов класса.
  • Универсальность. Основа стека — односвязный список. Следовательно, его размер ограничен только объёмом доступной оперативной памяти.
  • Инкапсуляция. Реализация методов класса отделена от контекста выполняемых им функций в теле программы.
  • Польза процесса. Быстро написать более простое решение, не разобравшись в тонкостях классической реализации, почти наверняка не удастся.

Недостатки

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

Related Images:

One thought on “e-olimp: 694. Минимум в очереди

Добавить комментарий