Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | deque.in, deque.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 1.225 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Deque
Se da un sir A cu N numere intregi. Pentru fiecare subsecventa de lungime K, sa se determine minimul, iar apoi sa se calculeze suma acestor minime.
Cerinta
Sa se afiseze suma ceruta.
Date de intrare
Pe prima linie a fisierului deque.in se afla numere N si K cu semnificatia din enunt. Pe urmatoarele N linii se afla cate un numar intreg din sirul dat.
Date de ieşire
În fişierul de ieşire deque.out se va afla un singur numar intreg reprezentand suma ceruta.
Restricţii si precizari
- 1 ≤ N ≤ 5 000 000
- 1 ≤ K ≤ N
- Elementele din sir vor avea valori cuprinse intre -10 000 000 si 10 000 000.
- Pentru rezultat se recomanda folosirea tipurilor intregi pe 64 de biti.
Exemplu
| deque.in | deque.out |
|---|---|
| 9 3 -7 9 2 4 -1 5 6 7 1 | -2 |
Explicaţie
Minimele corespunzatoare fiecarei subsecvente de lungime 3 sunt: -7 2 -1 -1 -1 5 1, suma acestora fiind -2.
Indicatii de rezolvare
O abordare brute-force in complexitate O(N2), ce determina minimele parcurgand pe rand fiecare secventa, obtine 20 de puncte [sursa aici]. Aceasta solutie poate fi imbunatatia, astfel incat cand se trece de la secventa care incepe pozitia i la cea de pe pozitia i+1, sa se recalculeze minimul doar daca acesta se afla pe pozitia i (acesta dispare din secventa curenta). Complexitatea ramane O(N2) si aceasta idee obtine 30 de puncte [sursa aici], dar pe teste aleatoare ruleaza comparabil cu solutia in complexitate O(N).
O alta idee de rezolvare se bazeaza pe faptul ca pentru a trece de la secventa care incepe pe pozitia i la cea care incepe pe pozitia i+1 dispare elementul de pe pozitia i si apare unul nou pe pozitia i+K. Pornind de la aceasta observatie, putem folosi un heap pentru a efectua stergerile si inserarile in complexitate O(logN) si pentru a afla minimul pentru un interval in O(1). In acest caz, complexitatea totala este O(NlogN) si o astfel de abordare ar trebui sa obtina 60 de puncte [sursa aici]. Este posibil ca folosind diverse optimizari, aceasta rezolvare sa obtina 100 puncte (motivul principal fiind cantitatea datelor de intrare).
Solutia optima, in complexitate O(N), foloseste o coada cu doua capete (double ended queue, deque). In aceasta structura, valorile noi pot fi inserate doar la sfarsitul cozii, in timp ce elementele existente pot fi eliminate atat pe la inceputul, cat si pe la sfarsitul deque-ului; toate aceste operatii avand loc in timp constant. Se observa ca daca exista doua elemente A[j] ≥ A[i] cu j < i, atunci A[i] va fi mereu preferat pentru minim fata de A[j], pentru secventele ce incep dupa pozitia i (inclusiv). Din acest motiv, la fiecare pas i, elementul curent A[i] elimina de la finalul deque-ului toate elementele ≥ cu el, apoi este inserat la finalul cozii. In acest fel, elementele din deque sunt mentinute in ordine crescatoare, deci minimul se va afla la inceput. Se elimina minimul cat timp acesta nu mai apartine secventei curente (pozitia lui este ≤ i-K). In final, se aduna minimul la solutie. O implementare a acestei structuri de date se gaseste aici.
Aplicatii
Aceasta structura de date poate fi adaptata intr-o larga varietate de probleme. In
