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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <cstdio> #include <queue> #include <algorithm> using namespace std; int main() { unsigned n; scanf("%u", &n); //количество команд int* to_sort = new int[n]; //исходный массив for(int i = 0; i < n; i++) scanf("%d", to_sort + i); unsigned k; scanf("%u", &k); //количество очередей queue<int>* sorting_machine = new queue<int>[k]; //массив очередей int *order = new int[n]; //порядок размещения чисел по очередям for(int i = 0; i < n; i++){ //подходящая очередь либо пуста, либо имеет последний элемент, меньший данного //найти её номер в массиве int available = find_if(sorting_machine, sorting_machine + k, [&](const queue<int> &q){return q.empty() || q.back() <= to_sort[i];}) - sorting_machine; //если таких очередей нет, то сортировка невозможна if(available >= k){ puts("NO"); return 0; } //добавить элемент массива в одну из очередей sorting_machine[available].push(to_sort[i]); order[i] = available + 1; } puts("YES"); for(int i = 0; i < n; i++){ //вывод порядка размещения исходного массива чисел по очередям printf("I(%d)\n", order[i]); } for(int i = 0; i < n; i++){ //так как и очередей, и элементов мало, найти минимальный доступный элемент queue<int>* minimum = min_element(sorting_machine, sorting_machine + k, [&](const queue<int> x, const queue<int> y){ return !x.empty() && !y.empty() && x.front() < y.front(); }); minimum->pop(); //удалить его //и вывести номер соответствующей очереди printf("R(%d)\n", minimum-sorting_machine+1); } return 0; } |
Детали реализации:
В коде программы активно используется библиотека [latex]algorithm[/latex] и анонимные функции,
объявленные по месту использования (внутри соответствующих методов), что позволяет минимизировать число лишних сущностей
и сделать реализацию более декларативной.
- find_if() — найти первый элемент участка контейнера, удовлетворяющий логическому условию. Принимает итераторы
на левую и правую границу интересующего участка, а также унарное логическое условие. Возвращает итератор на интересующий
элемент или итератор на область за пределами участка, если условие не выполнилось ни разу. - min_element() — найти минимальный элемент на заданном участке контейнера. Принимает итераторы на левую и правую
границу интересующего участка и двухместный предикат, задающий отношение порядка. Возвращает итератор на интересующий
элемент или за на область за пределами участка, если условие не выполнилось ни разу (пустой контейнер, некорректный порядок).