15159. Balony [AL_07_10]

Zadanie:
https://pl.spoj.com/problems/AL_07_10

Skrócony opis problemu:

Dane jest $n$ sal, $m$ pomocników oraz ilość uczestników konkursu $x_i$ w każdej z $n$ sal. W każdej sali musi być przynajmniej 1 pomocnik. Oblicz maksymalną ilość uczestników przypadającą na jednego pomocnika zakładając optymalne rozmieszczenie pomocników. Innymi słowy musisz tak poprzydzielać pomocników do sal, aby zminimalizować maksymalną ilość uczestników na pomocnika.

Np. dla $n=3, m=6$ i $x = [10, 30, 90]$ wynikiem jest 30, bo do pierwszej sali przydzielamy 1 pomocnika i: albo do drugiej 1, a do trzeciej 4 - wtedy w drugiej 1 pomocnik musi radzić sobie z 30 uczestnikami, albo do drugiej 2, a do trzeciej 3 - wtedy w trzeciej sali jest 3 pomocników na 90 uczestników (czyli każdy pomocnik ma przydzielonych 30 uczestników).

Rozwiązanie naiwne:

Dla każdego pomocnika szukamy liniowo sali, w której jest największy stosunek uczestników do pomocników i tam go przydzielamy.

Złożoność: $O(nm)$, bo dla każdego z $m$ pomocników sprawdzamy każdą z $n$ sal.

Rozwiązanie sprytniejsze:

Możemy przyspieszyć powyższy algorytm szybciej przeszukując wszystkie sale. Wystarczy utworzyć seta, w którym przechowywane będą pary (ilość pomocników $p$, ilość uczestników $u$) dla każdej sali. Dla każdego pomocnika będziemy zatem szukać w czasie stałym elementu o największym stosunku $u$ do $p$, a następnie modyfikować ten element w czasie logarytmicznym (jako że modyfikacja jest w czasie stałym, ale aktualizacja seta w czasie logarytmicznym). Na koniec bierzemy element o największym stosunku i wypisujemy ten stosunek.

Należy pamiętać, że przy obliczaniu stosunku należy wynik zaokrąglać w górę.

Złożoność: $O(m \log n)$, jako że dla każdego z $m$ pomocników sprawdzamy w czasie $O(\log n)$, do której sali powinien pójść.

Algorytm:

struct para
{
    int x, y;
    bool operator<(const para &a)const
    {
        return (double)x*(double)a.y > (double)a.x*(double)y; // korzystamy z mnożenia zamiast dzielenia, żeby nie było problemów z precyzją
    }
};

int main()
{
    int n, m, i;
    multiset<para>::iterator it;
    para room;

    get(n, m);
    multiset<para> rooms;
    m -= n; // n pomocników jest od razu przydzielonych do każdej sali po jednym
    for(i = 0; i < n; ++i)
        get(room.x),
        room.y = 1,
        rooms.insert(room);
    while(m--)
    {
        it = rooms.begin();
        room.x = (*it).x; room.y = (*it).y+1;
        rooms.erase(it);
        rooms.insert(room);
    }
    it = rooms.begin();
    print(ceil((double)(*it).x/(double)(*it).y));
}

Rozwiązanie najsprytniejsze:

Powyższe rozwiązanie jest dosyć wolne dla rozmiarów danych z zadania. Możemy zauważyć, że da się zmienić zmienną $m$, która stoi przed logarytmem w poprzednim zadaniu, na mniejszą. Możemy więc zrobić wyszukiwanie binarne po wyniku. Oznacza to, że wybieramy sobie kolejne wyniki i dla niego próbujemy dobrać jak najlepsze dane. W tym przypadku dla każdego rozpatrywanego wyniku (czyli stosunku uczestników do pomocników) będziemy próbowali wykorzystać minimalną ilość pomocników $x$ do otrzymania takiego stosunku. Wyniki będą z przedziału od 1 (najlepszy możliwy stosunek) do $max$, który oznacza maksymalny rozmiar sali (czyli najgorszy stosunek oznaczający, że w najbardziej zatłoczonej sali jest tylko 1 pomocnik). Zaczynamy od wyniku $w$ będącym połową przedziału, czyli $\frac{max}{2}$. Jeśli $x < m$, to znaczy, że zostało nam $m-x$ pomocników, których nie wykorzystujemy. Tak więc wiemy, że wynik ostateczny jest mniejszy lub równy $w$, bo być może tymi pozostałymi pomocnikami uda się zmniejszyć największy stosunek. Tak więc aktualizujemy wynik na połowę nowego przedziału: $\left<1;w\right>$. $w$ jest zatem równe: $\frac{1+w}{2}$. Teraz okazuje się z kolei, że $x > m$, ergo aby otrzymać wynik $w$ potrzebowalibyśmy $x$ pomocników, a tylu nie mamy. Wynik ostateczny będzie zatem większy od $w$, gdyż stosunek będzie większy (gorszy) niż $w$. Aktualizujemy zatem $w$ idąc tym razem w prawo, czyli biorąc większe $w$, które dla przedziału $\left<1;w\right>$ będzie równe $\frac{\frac{1+w}{2}+w}{2}$.

No i szukamy tak długo optymalnego $w$ aż wyjdzie nam, że $x=m$.

Pozostaje jeszcze problem znalezienia minimalnej ilości pomocników potrzebnej do uzyskania danego wyniku (stosunku). Jak to zrobić? Ano przechodzimy po prostu każdą salę i sprawdzamy ilu minimalnie potrzeba pomocników, aby w danej sali był stosunek (wynik), który aktualnie rozpatrujemy. Tak więc mając stosunek $s$ i ilość uczestników w danej sali $u$ obliczamy $\left(\lceil\frac{u}{s}\rceil\right)$ i bierzemy maksimum z wyników dla każdej sali (czyli maksymalną ilość pomocników w salach).

Złożoność: $O(n \log max)$, gdyż wyszukujemy binarnie (a więc w czasie logarytmicznym) wynik z przedziału $\left<1;max\right>$ i dla każdego z wyników obliczamy w $O(n)$ ilu minimalnie pomocników potrzeba do otrzymania danego wyniku.

Uwaga: Nie możemy skorzystać z funkcji lower_bound, gdyż trzeba by najpierw wypełnić tablicę, bo której będziemy przeszukiwać w czasie $O(m)$. Złożoność wynosiłaby wtedy: $O(m + n \log max)$.

Ostateczny algorytm:

int tab[500005], n, m;

int lower_bound(int a, int b)
{
    if(a == b)
        return a;
    int c = (a+b)/2, s = 0, i;
    for(i = 0; i < n; ++i)
        s += ceil((double)tab[i]/(double)c);
    if(s > m)
        return lower_bound(c+1, b);
    else
        return lower_bound(a, c);
}

int main()
{
    int i, maxx;
    
    get(n, m);
    for(maxx = i = 0; i < n; ++i)
    {
        get(tab[i]);
        if(tab[i] > maxx)
            maxx = tab[i];
    }
    print(lower_bound(1, maxx));
}

Wersja iteracyjna z tą samą złożonością:

int main()
{
    int n, m, i, maxx, a, b, c, s, tab[500005];
    
    get(n, m);
    for(maxx = i = 0; i < n; ++i)
    {
        get(tab[i]);
        if(tab[i] > maxx)
            maxx = tab[i];
    }
    a = 1; b = maxx;
    while(a < b)
    {
        s = 0; c = (a+b)/2;
        for(i = 0; i < n; ++i)
            s += ceil((double)tab[i]/(double)c);
        if(s > m)
            a = c+1;
        else
            b = c;
    }
    print(a);
}

Ciekawostka: Zamiast funkcji ceil z math.h można użyć wzoru $\frac{a+b-1}{b}$, który jest odpowiednikiem $ceil((double)a/(double)b)$ lub wzoru $\frac{a}{b}+(a \mod b \neq 0)$. Przyspieszy to znacznie (w tym wypadku) program, gdyż będziemy operować na intach, a nie doublach. Pierwszy wzór nie działa dla liczb ujemnych oraz trzeba z nim uważać na przekroczenie wartości inta. Jest za to lekko szybszy od ostatniego wzoru, gdyż nie korzysta z modulo, które jest wolniejsze od dodawania i odejmowania.