Kolejka monotoniczna

pytanie zadane 21 maja 2023 w C i C++ przez Dani Obywatel (1,450 p.)

Cześć, macie jakieś fajne materiały edukacyjne do kolejki monotonicznej?

1 odpowiedź

odpowiedź 21 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
wybrane 21 maja 2023 przez Dani

Najlepsza

Zacznijmy od tego co to jest kolejka monotoniczna, jest to struktura danych, na której chcemy trzymać minimum/maximum itp. Na przedziale, który pełznie jak gąsienica. Sama jej idea jest bardzo prosta. Załóżmy że chcesz mieć kolejkę monotoniczna minów. Jeśli dodajesz jakiś element A[i], to wywalasz wszystkie elementy > A[i], bo one nigdy nie będą minem. Jeśli usuwasz element to sprawdzasz czy najmniejszy na całej kolejce = A[i], jak tak to go usuwasz. A odwołanie do mina to Q.front(),o ile implementujesz na deque w c++. Te procedury dodaj, usuń, odczytaj mina mają po kilka linijek, to jest naprawdę takie proste.

Zadania na nią to np:

- Temperatura OI

- Wilcze Doły OI

- Fajnym ćwiczeniem jest zadanie: masz tablice A, dla każdego elementu wyznacz pierwszy mniejszy na lewo. (Można też drzewem przedziałowym)

- Jest też bardzo fajne zadanie Prawnicy z OI, ono nie jest na kolejkę monotoniczna, ale bardzo polecam.

Warte podkreślenia jest, że kolejkę monotoniczna można praktycznie zawsze zastąpić setem/multisetem, ale jest wolniejsze bo dziala w logu.

komentarz 22 maja 2023 przez Dani Obywatel (1,450 p.)

Jaką złożoność miała by taka kolejka?

1	komentarz 22 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.) Każdy element maksymalnie raz dodasz i maksymalnie raz z niej weźmiesz, czyli O(N).