Solutia problemei Petreceri

Subtask 1:

Se observa ca mereu este optim consumul celei mai ieftine unităţi de lapte care poate fi adusă la o petrecere.

O observaţie importantă pentru soluţia finala a problemei poate fi dedusă dacă se redefineşte achiziţionarea unei noi unităţi. Nu face nicio diferenţa dacă pentru o sticlă de lapte se plăteşte înainte de a o consuma sau la petrecerea de unde a fost cumpărată. Astfel se pot ţine minte cele mai bune preţuri ale unităţilor de lapte la care are Rick acces în fiecare moment şi se va adaugă la rezultat doar cantitatea băută. Când se ajunge la o noua petrecere se vor arunca toate unităţile mai scumpe decât cele vândute acolo, se vor consuma din cele mai ieftine a[i] unităţi(completând cu băuturi se cost c[i] dacă e necesar) şi se vor înlocui unităţile dispărute cu unităţi de preţ c[i]. Greedy-ul este corect deoarece nu merită sa se consume o unitate de lapte mai scumpă dacă altele mai ieftine pot fi luate. Pentru asta se poate folosi o coada(deque).
Deoarece fiecare unitate consumata trebuie considerata şi rămân t unităţi complexitatea este O(t+\sum_{i=1}^{n} a[i]) \equiv O(n\cdot t) . 

Subtask 2:

Pentru 30 de puncte se pot parcurge petrecerile în ordine crescătoare a preţurilor şi se vor transporta mai multe unităţi de lapte către petrecerile care urmează. Pentru a face asta se va tine minte, pentru fiecare petrecere, T[i], numărul maxim de unităţi de lapte pe care le mai poate duce Rick către petrecerea i+1. Astfel, pentru fiecare petrecere se vor modifica succesorii dacă permite şirul T.

Subtask 3:

La soluţia primului subtask se observa ca nu este necesara stocarea fiecărei unităţi în parte ci se poate tine minte frecventa unităţilor cu acelaşi preţ. Operaţiile de mai sus se pot face cu un set de perechi de tip (valoare, frecventa). Complexitatea noua este O(n \log_2{n}) .

Subtask 4:

Operaţiile făcute în soluţia anterioara cu un set(găsirea şi eliminarea maximelor şi a minimelor si adăugarea de elemente mai mari decât toate celelalte considerate) se pot face cu o coadă cu operaţii la ambele capete(deque). Unităţile şi frecvenţele lor vor fi reţinute în ordinea crescătoare a preţurilor.
Complexitatea finală este O(n) .