Kolejka monotoniczna

Kolejka monotoniczna

Kolejkę monotoniczną (kolejka minimów, kolejka maksimów) wykorzystujemy do określania jaka jest aktualnie najmniejsza (największa) wartość w kolejce FIFO. Odpowiedź uzyskujemy w czasie stałym, natomiast złożoność czasowa tworzenia kolejki monotonicznej jest liniowa w stosunku do rozpatrywanych wartości. Do jej utworzenia wykorzystamy dwukierunkową kolejkę deque.

Zadanie

Napisz program, który będzie wykonywał jedną z trzech czynności:

• wstawianie elementu na koniec kolejki
• usuwanie elementu z przodu kolejki
• określanie wartości najmniejszej (największej) spośród aktualnych wartości w kolejce

Wejście

W pierwszym wierszu jedna liczba q określająca liczbę operacji (nie większa niż 10⁷).

W kolejnych q wierszach czynność, która może być następującej postaci:

• 0 [wartość] — wstawienie wartości na koniec kolejki (dodatnia wartość nie większa niż milion)
• 1 — usunięcie wartości z końca kolejki
• 2 — podanie najmniejszej (największej) wartości w kolejce.

Wyjście

Dla każdego zapytania 2 wypisanie najmniejszej (największej) wartości w kolejce.

//algorytm.edu.pl
//kolejka monotoniczna (kolejka minimów, kolejka maksimów)
#include<bits/stdc++.h>
using namespace std;

//dodanie elementu do kolejki
//argumenty: wartość, pozycja z pierwotnego ciągu, kolejka
void push_(int val, int pos, deque<pair<int, int> > &kolejka)
{
	//usunięcie wszystkich elementów z końca kolejki
	//której wartości są nie mniejsze od wstawianej wartości
	while(!kolejka.empty() && kolejka.back().first >= val) 
		kolejka.pop_back();
		
	kolejka.push_back({val, pos});
}

//usunięcie elementu z przodu kolejki i jej aktualizacja
//argumenty: pozycja pierwszego elementu w kolejce, kolejka
void pop_(int pos, deque<pair<int, int> > &kolejka)
{
	if(!kolejka.empty() && kolejka.front().second == pos)
		kolejka.pop_front();
}

//odczytanie aktualnie najmniejszej wartości w kolejce
int print_min(deque<pair<int, int> > &kolejka)
{
	return kolejka.front().first;
}

int main()
{
	deque <pair<int, int> > kolejka;
	int q, opcja, val, pos, 
		p = 0; //numer elementu z początku kolejki
	cin>>q; //wczytanie liczby operacji
	for(int i=0; i<q; i++)
	{
		cin>>opcja; //0 - dodanie wartości val na koniec kolejki
					//1 usunięcie pierwszego elementu z kolejki
					//2 - wypisanie minimum
		switch(opcja)
		{
			case 0:
				cin>>val;
				push_(val, i, kolejka);
				//push_(-val, i, kolejka); //gdy szukamy maksimum
				break;
			case 1:
				pop_(p++, kolejka);
				break;
			case 2:
				cout<<print_min(kolejka)<<endl;
				//cout<<-print_min(kolejka)<<endl; //gdy szukamy maksimum
				break;
		}
	}
	
	return 0;
}

Przykład:

Wejście:

11
0 3
0 2
0 5
0 3
2
1
1
2
0 1
0 5
2

Wyjście:

2
3
1