Problema BR – ONI 2009, Clasa a 9-a

• Dificultate:
• Autor: Cristian George Strat
• Online: 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';
    }
    return 0;
}

Dacă ai vreo nedumerire cu privire la problema BR, lasă un comentariu și te voi ajuta