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$.
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ă.
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:
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++
#include <fstream>
#define NMAX 15010
std::ifstream fin("br.in");
std::ofstream fout("br.out");
int n, t;
int ps[NMAX];
int main() {
fin >> n >> t;
for (int i = 1; i <= n; i++) {
fin >> ps[i];
ps[i] += ps[i - 1];
}
for (int it = 0; it < t; it++) {
int k, x;
fin >> k >> x;
if (x >= ps[n]) {
fout << n << '\n';
continue;
}
int sol = 0;
if (ps[n] - ps[k - 1] <= x) {
sol += n - k + 1;
x -= ps[n] - ps[k - 1];
k = 1;
}
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;
}
sol += lo - k + 1;
fout << sol << '\n';
}
fout.close();
return 0;
}
Dacă ai vreo nedumerire cu privire la problema br, lasă un comentariu și te voi ajuta