Enunțul problemei br, de clasa a 9-a, dată în 2009 la ONI, se găsește pe .campion și InfoArena.
Rezumat br
La o masă rotundă sunt așezați n prieteni care beau bere fără alcool. Berea preferată a fiecărui prieten i are costul c[i]. Din când în când, un prieten cumpără câte o bere pentru o secvență de prieteni aflați pe poziții consecutive la masă, în sensul acelor de ceasornic, începând cu el. Să se răspundă la t întrebări de forma k x cu semnificația: Care este numărul maxim de beri pe care le poate cumpăra prietenul k folosind maxim x bani? Se vor cumpăra maxim n beri.
Soluție br
În primul rând, vom calcula vectorul de sume parțiale ps pentru vectorul c, pentru a putea mai apoi să determinăm în $O(1)$ suma valorilor pe anumite secvențe. Rezolvăm fiecare întrebare individual. În primul rând, observăm că dacă x >= ps[n], atunci se pot cumpăra beri pentru toți prietenii, așa că afișăm direct n.
|
1 2 3 4 |
if (x >= ps[n]) { fout << n << '\n'; continue; } |
Dacă nu, având în vedere că masa este circulară, s-ar putea ca secvența căutată să treacă prin n, iar apoi prin 1, ceea ce ne-ar îngreuna căutarea capătului din dreapta. (Asta se poate întâmpla cel mult o singură dată, căci altfel ne-am încadra în cazul x >= ps[n].) Pentru a verifica acest lucru, testăm dacă ps[n] - ps[k - 1] <= x. Dacă da, scădem ps[n] - ps[k - 1] din x, adăugăm n - k + 1 la soluție, și ne rămâne să rezolvăm aceeași problemă pentru noul x și k = 1. Rezultatul îl vom adăuga la soluția curentă.
|
1 2 3 4 5 |
if (ps[n] - ps[k - 1] <= x) { sol += n - k + 1; x -= ps[n] - ps[k - 1]; k = 1; } |
Ne-am simplificat problema: Acum trebuie să găsim capătul din dreapta p al unei secvențe de lungime maximă ce începe cu k, astfel încât ps[p] - ps[k - 1] <= x, știind că k <= p <= n. Se poate observa ușor că sumele parțiale formează un șir crescător, deoarece costurile berilor sunt pozitive. Asta înseamnă că pentru p = k, k + 1, …, n, valorile ps[p] - ps[k - 1] sunt în ordine crescătoare. Așadar, putem face o simplă căutare binară pe rezultat, astfel:
|
1 2 3 4 5 6 7 8 |
int lo = k - 1, hi = n + 1; while (hi - lo > 1) { int md = (lo + hi) / 2; if (ps[md] - ps[k - 1] > x) hi = md; else lo = md; } |
La final, rezultatul, adică p, se va afla în lo.
Complexitatea algoritmului este $O(n + t \cdot \log_2 n)$.
Sursă C++ br
Dacă ai vreo nedumerire cu privire la problema br, lasă un comentariu și te voi ajuta 🙂
Îți place conținutul acestui site?
Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!