e-olimp: 694 — Минимум в очереди
Постановка задачи
На вход программы подается набор операций с очередью. Каждая операция состоит в добавлении или удаления элемента из очереди. После выполнения каждой операции найдите наименьшее число, которое находится в очереди. Сложите все полученные числа и получите ответ. Если после некоторой операции очередь оказалась пуста, то ничего не прибавляйте к ответу. Если выполнить удаление невозможно, так как очередь пуста, то не выполняйте его.
Алгоритм решения
Классическая модификация очереди с поддержкой минимального хранимого значения подразумевает использование двух модифицированных стеков, один из которых служит только для проталкивания элементов в очередь, а другой — только для выталкивания. Стеки хранят пары значений: непосредственно элемент и минимальное значение в очереди на момент его добавления, что позволяет поддерживать актуальную информацию при выполнении модифицирующих запросов (см. классический труд Кормена и статью на e-maxx). Более подробно механика процесса описана в комментариях к коду.
Реализации:
На примере предложенной задачи можно наглядно продемонстрировать различия между стилем программирования, применяемым на соревнованиях, и более вдумчивым, практически ориентированным подходом.
Спортивный подход
ideone: http://ideone.com/pvVixS
засчитанное решение: http://www.e-olimp.com/solutions/1926658
|
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 49 50 51 52 |
#include <cstdio> #include <cstdlib> #include <algorithm> using namespace std; typedef long long ll; int main(){ unsigned n; scanf("%u", &n); ll a, b, c, x, sum = 0; scanf("%lld %lld %lld %lld", &a, &b, &c, &x); unsigned capacity = unsigned(1e6); ll *head = (ll*)calloc(capacity + 1, sizeof(ll)); //стек, из которого удаляют элементы ll *hmin = (ll*)calloc(capacity + 1, sizeof(ll)); //его локальные минимумы ll *tail = (ll*)calloc(capacity + 1, sizeof(ll)); //стек, в который добавляют элементы ll *tmin = (ll*)calloc(capacity + 1, sizeof(ll)); //его локальные минимумы ll r = 0, l = 0; //позиции в первом и втором стеках while(n--){ x = (a*x*x + b*x + c)/100 % 1000000; //подсчет нового значения Х if(x % 5 < 2){ if(l == 0){ //если голова пуста hmin[1] = head[1] = tail[r]; //инициализация головы очереди for(l = 2; l <= r; l++){ //переносим элементы из первого стека во второй, из хвоста в очередь (в обратном порядке) head[l] = tail[r - l + 1]; //реализация обратного порядка обхода hmin[l] = min(hmin[l-1], head[l]); //минимум на данном шаге равен минимуму из предыдущего и текущего } r = 0; //хвост очереди очищен l--; //голова перезаписана } l--; //сдвиг влево на текущую позицию } else{ tail[++r] = x; //записать x в хвост if(r == 1) //если очередь состоит из одного элемента tmin[r] = x; //то он же и является минимальным else tmin[r] = min(tmin[r-1], x); //иначе оптимальный элемент равен минимуму из того, что было, и нового элемента } if(r > 0 && l > 0) //если и голова, и хвост непусты sum += min(tmin[r], hmin[l]); //то добавить к сумме минимум из значений в голове и хвосте else if(r > 0 && l == 0) sum += tmin[r]; else if(r == 0 && l>0) sum += hmin[l]; } printf("%lld\n", sum); return 0; } |
Преимущества
- Простота. Концепция воплощается буквально — даже в условиях ограниченности во времени ошибиться трудно.
- Наглядность и компактность кода.
- Сообразность средств цели: постановка задачи требует реализации только трех функций: проталкивания, выталкивания и взятия крайнего элемента. Каждая из них реализована по возможности наиболее простым способом.
Недостатки
- Немасштабируемость. При необходимости внедрения дополнительного функционала или изменении постановки задачи (скажем, отсутствии явной верхней границы для входных данных) возникают проблемы, решение которых неизбежно приводит к использованию объектно-ориентированных средств языка.
- Перерасход памяти. Реальное количество одновременно содержащихся элементов в каждом из стеков на порядок меньше, но из формулировки задания это не следует и выясняется экспериментальным путём.
- Костыли, избыточные сущности. Отличительная черта одноразового кода. Во время соревнования требования к коду достаточно мягкие: он должен работать. Желательно — предсказуемым образом. Причем, нередко реализуется не оптимальное и логичное решение, а то, которое понимаешь. Отладка и чтение таких программ — занятие не из приятных.
Объектно-ориентированный подход
ideone: http://ideone.com/A6BpwN
засчитанное решение: http://www.e-olimp.com/solutions/1924823
|
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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 |
#include <iostream> #include <cstdlib> //calloc() #include <utility> //pair #include <algorithm> //min(), max() using namespace std; const int capacity = 100; //ёмкость каждого узла списка template <class T> //T - тип данных, хранящихся в стеке class stack{ private: struct node{ //основа стека неограниченной вместительности - односвязный список массивов node* prev; //указатель на предыдущий узел T* storage; //массив данных, хранящихся в текущем узле node(){ //конструктор по умолчанию prev = nullptr; //список содержит всего один узел storage = (T*)calloc(capacity+1, sizeof(T)); //выделить память под capacity элементов заданного типа } node(node* predecessor){ //параметрический конструктор: добавление нового узла в список prev = predecessor; //последний узел старого списка будет предшественником нового узла storage = (T*)calloc(capacity+1, sizeof(T)); //в отличие от malloc, calloc заполняет выделенный участок памяти нулями } ~node(){ //деструктор free(storage); //очистить участок памяти, в котором хранится текущий узел } }; node* container; //односвязный список int pos; //текущая позиция указателя. Используется 1-индексация массивов. int stored; //количество хранимых в данный момент элементов public: stack(){ //конструктор по умолчанию container = new node(); //создать список из одного узла pos = stored = 0; //0 - служебная позиция, сигнализирующая о том, что стек пуст } //(в решении задачи не используется, но объявлять конструктор без деструктора - дурной тон - прим.) ~stack(){ //деструктор while(container != nullptr){ //пока список не пуст node* predecessor = container->prev; //сохранить указатель на предшествующий узел delete container; //очистить текущий узел container = predecessor; //перейти к предшествующему узлу } pos = stored = 0; //сбросить счетчик и указатель на позицию в стеке } bool empty(){ //проверка на пустоту return stored == 0; } int size(){ //количество элементов в стеке return stored; } T top(){ //крайний элемент стека return container->storage[pos]; } void push(T x){ //добавление элемента if(pos == capacity){ //если текущий узел заполнен container = new node(container); //создать новый узел pos = 0; //и явно указать, что он пуст } container->storage[++pos] = x; //добавить элемент в стек ++stored; //количество хранимых элементов увеличилось на 1 } void pop(){ //удаление элемента if(pos == 1 && stored >= capacity){ //извлекается последний элемент крайнего узла списка node* predecessor = container->prev; //сохранить указатель на предыдущий узел delete container; //очистить память, занимаемую пустым узлом container = predecessor; //обновить указатель на текущий узел pos = capacity + 1; //удаление элемента эквивалентно сдвигу указателя влево //во избежание дублирования участка кода, указателю было присвоено значение //сдвигом влево которого будет получен указатель на крайний элемент узла } --stored; //число хранимых элементов уменьшается на единицу --pos; //указатель на текущую позицию сдвигается на единицу влево } void clear(){ //очистка содержимого стека while(container != nullptr){ //если список не пуст node* predecessor = container->prev; //сохранить указатель на предшествующий узел delete container; //очистить текущий узел container = predecessor; //перейти к предшествующему узлу } container = new node(); //в отличие от деструктора, в списке оставляется один узел pos = stored = 0; //сброс значений счетчика и указателя на текущую позицию } }; //модифицированные стеки: первый элемент пары - хранимое значение, второй - минимум в данной позиции stack<pair<long long, long long>> head, tail; //голова и хвост очереди //head - стек, из которого только удаляют элементы //tail - стек, в который только добавляют элементы int main(){ int n; cin >> n; //количество операций с очередью long long a, b, c, x, min_sum = 0; cin >> a >> b >> c >> x; while(n--){ x = (a*x*x + b*x + c)/100 % 1000000; if(x % 5 < 2){ //удалить элемент из очереди if(head.empty()){ //если соответствующий стек пуст while(!tail.empty()){ //то перебросить в него содержимое другого стека long long value = tail.top().first; tail.pop(); long long minimum = head.empty() ? value : min(head.top().second, value); head.push({value, minimum}); } //по окончании обмена принцип FIFO не нарушен, так как элементы //хвоста очереди расположены в голове в порядке, обратном исходному } if(!head.empty()) //если очередь непуста head.pop(); //удалить первый элемент очереди } else{ //добавить элемент в очередь if(tail.empty()) //если соответствующий стек пуст tail.push({x, x}); //то добавленный элемент также является текущим минимумом else //в противном случае tail.push({x, min(x, tail.top().second)}); //если добавленный элемент меньше всех, содержащихся в стеке //то обновить текущий минимум } if(tail.empty() ^ head.empty()) //если не пуст или первый, или второй стек (но не оба одновременно) min_sum += tail.empty() ? head.top().second : tail.top().second; //прибавить к сумме доступный минимум else //если оба стека одновременно либо пусты, либо нет min_sum += tail.empty() ? 0 : min(tail.top().second, head.top().second); //либо не изменить сумму, либо добавить к ней минимум //из значений, хранящихся в обоих стеках } cout << min_sum << endl; //минимально возможная после всех манипуляций сумма } |
Преимущества
- Масштабируемость. Добавление функционала сводится к написанию новых методов класса.
- Универсальность. Основа стека — односвязный список. Следовательно, его размер ограничен только объёмом доступной оперативной памяти.
- Инкапсуляция. Реализация методов класса отделена от контекста выполняемых им функций в теле программы.
- Польза процесса. Быстро написать более простое решение, не разобравшись в тонкостях классической реализации, почти наверняка не удастся.
Недостатки
- Временные затраты. Использование односвязного списка порождает частные случаи, на которые придется обратить внимание. Их классификация и обработка требует вдумчивого подхода.
Отличная статья получилась, молодец!