(Categoria _Structuri de date_, Autor _Xulescu_)
(toc){width: 27em}*{text-align:center} *Conţinut:*

* 'Introducere':deque-si-aplicatii#introducere

* '_Introducere_':deque-si-aplicatii#introducere

* '1. Book Pile (SGU)':deque-si-aplicatii#problema-1
* '2. Vila 2 (.campion)':deque-si-aplicatii#problema-2
* '3. Şir':deque-si-aplicatii#problema-3

* '5. Otilia (.campion)':deque-si-aplicatii#problema-5
* '6. Bcrc (Stelele Informaticii 2006)':deque-si-aplicatii#problema-6
* '7. Cut the Sequence (PKU)':deque-si-aplicatii#problema-7

* 'Concluzii':deque-si-aplicatii#concluzii
* 'Probleme suplimentare':deque-si-aplicatii#probleme-suplimentare
* 'Bibliografie':deque-si-aplicatii#bibliografie

* '_Concluzii_':deque-si-aplicatii#concluzii
* '_Probleme suplimentare_':deque-si-aplicatii#probleme-suplimentare
* '_Bibliografie_':deque-si-aplicatii#bibliografie

În acest articol voi prezenta o structură de date de tip listă numită _deque_. Simplitatea acestei structuri poate nu are multe de spus şi din acest motiv am prezentat şi o serie de aplicaţii care vor arăta neaşteptata sa utilitate şi apariţie în locurile unde am fi crezut că nu se mai poate face nimic pentru a reduce complexitatea.

În multe aplicaţii unde soluţiile parţiale se reprezintă sub forma unui şir continuu de valori care permite inserarea şi ştergerea doar pe la capete (în general inserări pe la un capăt şi ştergeri pe la celălalt) se poate folosi un deque. Să urmărim în continuare cazuri concrete în care simplitatea unui deque duce la soluţii de multe ori optime şi implementări foarte scurte şi clare.

h2(#problema-1). 'Book Pile':http://acm.sgu.ru/problem.php?contest=0&problem=271 (SGU)

h2(#problema-1). '1. Book Pile':http://acm.sgu.ru/problem.php?contest=0&problem=271 (SGU)

bq. Se dau $N$ cărţi aşezate una deasupra celeilalte asupra cărora se vor efecta $M$ operaţii de două tipuri: 1. $ADD${$(nume)$} : se adaugă cartea $nume$ deasupra celorlalte; 2. $ROTATE$ : primele $K$ cărţi de deasupra se rotesc (dacă sunt mai puţin de $K$ cărţi atunci se vor roti toate). Se cere să se afişeze cărţile în ordine, prima fiind cea de deasupra, după efectuarea celor $M$ operaţii.
Restricţii: $0 ≤ N, K ≤ 40 000$, $0 ≤ M ≤ 100 000$.

Întrucât operaţiile unui deque se execută în $O(1)$ amortizat, soluţia are complexitatea $O(N + M)$.

h2(#problema-2). 'Vila 2':problema/vila2 (.campion)

h2(#problema-2). '2. Vila 2':problema/vila2 (.campion)

bq. Se dă un şir $S$ de $N$ numere întregi şi un $D$ număr natural. Se cere să determine diferenţa maximă dintre oricare două numere din şir cu proprietatea că diferenţa indicilor nu depăşeşte $D$.
Restricţii: $2 ≤ N ≤ 100 000$, $1 ≤ D ≤ N/2$.

Cum fiecare indice din $1$, $2$, .., $N$ trece cel mult o dată prin deque complexitatea finală este $O(N)$ amortizat.

h2(#problema-3). 'Şir':problema/sir

h2(#problema-3). '3. Şir':problema/sir

bq. Se dă un şir $S$ de numere întregi de lungime $N$. Se cere să se găsească secvenţa de lungime maximă cuprinsă între $X$ şi $Y$ astfel încât $MAX - MIN ≤ Z$, unde $MAX$ este maximul dintre toate numerele întregi din secvenţă iar $MIN$ minimul dintre acestea. Secvenţa soluţie va fi cea cu poziţia de început maximă dintre toate secvenţele de lungime maximă.
Restricţii: $3 ≤ N ≤ 100 000$, $1 ≤ X ≤ Y ≤ N$, $0 ≤ Z ≤ 30 000$.

Complexitatea finală va fi $O(N)$.

h2(#problema-4). 'Trans':problema/trans (ONI 2004)

h2(#problema-4). '4. Trans':problema/trans (ONI 2004)

bq. Se dau $N$ blocuri de piatră, de culoare albă sau neagră aşezate în ordinea $1$, $2$,.., $N$. Blocurile de piatră trebuie să fie transportate în ordinea în care sunt, iar pentru aceasta va trebui închiriat un camion. Se mai dau $Q$ tipuri de camioane. Camionul de tipul $i (1 ≤ i ≤ Q)$ poate transporta maxim $K{~i~}$ blocuri de piatră la un moment dat şi pentru un transport se percepe taxa $T{~i~}$. Se impune condiţia ca toate blocurile de piatră plasate în camion la un transport sa aibă aceeaşi culoare. Aşadar, pentru a fi transportate toate blocurile, se va alege un camion de un anumit tip, iar camionul va efectua unul sau mai multe transporturi. Pentru a micşora suma totală plătită, există posibilitatea de a schimba culoarea oricărui bloc de piatră (din alb în negru sau din negru în alb); pentru fiecare bloc $i (1 ≤ i ≤ N)$ se cunoaşte suma $S{~i~}$ ce trebuie plătită pentru a-i schimba culoarea $C{~i~}$.
Cerinţă: Pentru fiecare dintre cele $Q$ tipuri de camioane, determinaţi suma minimă plătită pentru a transporta toate cele $N$ blocuri.

}
==

h2(#problema-5). 'Otilia':problema/otilia  (.campion)

h2(#problema-5). '5. Otilia':problema/otilia  (.campion)

bq. Otilia şi Burbucel au o grămadă de $N$ pietre şi vor juca un joc cu următoarele trei reguli: 1. Primul jucător are voie să ia din gramadă cel mult $K$ piese; 2. Cu excepţia primei mutări, fiecare jucător are voie să ia maxim $P * t$ pietre, unde $t$ este numărul de pietre care au fost substituite din grămadă la mutarea precedentă; 3. Pierde cel care mută ultimul (cel care ia ultimele pietre din grămadă).
Cerinţă: Se dau $M$ jocuri prin numerele $N$, $K$ şi $P$. Se cere să se determină dacă Otilia va câştiga fiecare din jocuri sau nu.

Este evident că prima relaţie o implică pe cea de-a doua. În momentul acesta se poate construi următorul algoritm: având lista de poziţii care pot fi bune pentru $X$ (sortată descrescător) o căutăm pe cea mai mare ca valoare care este într-adevăr bună. În principiu, scoatem din capul listei poziţiile rele până când dăm de o poziţie bună. La listă se va adăuga şi $X$ şi se va trece la pasul următor. Operaţiile algoritmului sunt chiar operaţiile asupra unui deque.

h2(#problema-6). 'Bcrc':problema/bcrc (Stelele Informaticii 2006)

h2(#problema-6). '6. Bcrc':problema/bcrc (Stelele Informaticii 2006)

bq. Se consideră $N$ camere, numerotate de la $1$ la $N$, aşezate în cerc. Iniţial (la momentul de timp 0), ne aflăm în camera $1$. În fiecare moment de timp, putem alege să rămânem în camera în care ne aflăm sau să ne deplasăm într-o cameră vecină într-o unitate de timp. Se dă o listă de $M$ cutii ce conţin bomboane prin $T$, $C$ şi $B$: cutia apare la momentul $T$ în camera $C$ şi conţine $B$ bomboane. Cutia va dispărea la momentul $T + 1$.
Cerinţă: Cunoscând numărul de camere din labirint şi momentele de timp la care apar cutiile cu bomboane, determinaţi care este numărul maxim de bomboane pe care le putem culege.

Complexitatea finală: $O(M * N)$.

h2(#problema-7). 'Cut the Sequence':http://acm.pku.edu.cn/JudgeOnline/problem?id=3017 (PKU)

h2(#problema-7). '7. Cut the Sequence':http://acm.pku.edu.cn/JudgeOnline/problem?id=3017 (PKU)

bq. Se dă o secvenţă $S$ de numere întregi de lungime $N$. Va trebui să se împartă secvenţa în mai multe subsecvenţe astfel încât suma valorilor din fiecare parte să nu depăşească un număr întreg $M$ dat, iar dacă însumăm maximul din fiecare subsecvenţă să obţinem o sumă cât mai mică.
Restricţii: $0 < N ≤ 100 000$, $0 ≤ S{~i~} ≤ 1 000 000$.

# Cosmin Negruşeri, "_Probleme cu secvenţe_":probleme-cu-secvente
# Dana Lica, "_Arbori de intervale şi aplicaţii în geometria computaţională_":arbori-de-intervale

# 'C++ Reference, _deque_':http://www.cplusplus.com/reference/stl/deque/

# 'C++ Reference':http://www.cplusplus.com/