e-olimp 2510. Сортировка очередями

e-olimp 2510. Сортировка очередями

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

Рассматривается специальное устройство, содержащее входной поток, выходной поток и k очередей, пронумерованных числами от [latex]1[/latex] до [latex]k[/latex].

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

Программа должна содержать ровно [latex]2n[/latex] операций, каждая из которых либо читает число из входного потока и добавляет его в одну из очередей, либо извлекает число из одной из очередей и выводит его в выходной поток.

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

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

Реализация:

Ideone: http://ideone.com/X37iWg
Засчитанное решение: http://www.e-olimp.com/solutions/1935453

Детали реализации:

В коде программы активно используется библиотека [latex]algorithm[/latex] и анонимные функции,
объявленные по месту использования (внутри соответствующих методов), что позволяет минимизировать число лишних сущностей
и сделать реализацию более декларативной.

  1. find_if() — найти первый элемент участка контейнера, удовлетворяющий логическому условию. Принимает итераторы
    на левую и правую границу интересующего участка, а также унарное логическое условие. Возвращает итератор на интересующий
    элемент или итератор на область за пределами участка, если условие не выполнилось ни разу.
  2. min_element() — найти минимальный элемент на заданном участке контейнера. Принимает итераторы на левую и правую
    границу интересующего участка и двухместный предикат, задающий отношение порядка. Возвращает итератор на интересующий
    элемент или за на область за пределами участка, если условие не выполнилось ни разу (пустой контейнер, некорректный порядок).
Іванов Вячеслав Володимирович
Іванов Вячеслав Володимирович

Latest posts by Іванов Вячеслав Володимирович (see all)

One thought on “e-olimp 2510. Сортировка очередями