Enunțul problemei br, de clasa a 9-a, dată în 2009 la ONI, se găsește pe InfoArena.
Rezumat
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
Î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 \ge 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 \ge ps[n]$.) Pentru a verifica acest lucru, testăm dacă $ps[n] - ps[k - 1] \le 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] \le x$, știind că $k \le p \le 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, \ldots, 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++
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!