20178. Wstążki [AL_17_03]

Zadania:
https://spoj.com/ALGOLIGA/problems/AL_17_03
https://pl.spoj.com/problems/AL_17_03

Skrócony opis problemu:

Mając $n$ wstążek o określonych długościach, należy podzielić je tak, by $m$ osób otrzymało kawałek i by zmaksymalizować najmniejszy z nich.

Rozwiązanie:

Możemy próbować jakoś szacować ilość kawałków, na które musimy podzielić daną wstążkę bazując np. na jej stosunku do sumy długości. Nigdy nie będzie to jednak wystarczająco dokładne. Potrzebujemy czegoś pewnego.

Pomyślmy, co możemy wydedukować z treści? Otóż wynik na pewno nie będzie większy niż $\frac{suma \ długości \ wstążek}{m}$. Dlaczego? Bo najlepszym scenariuszem będzie jak zużyjemy każdy kawałek wstążki, a skoro mamy $m$ osób, to najlepiej by było jakby każda dostała równy kawałek. A więc mamy górne ograniczenie. A co z dolnym? No może się zdarzyć, że każda z osób dostanie po 0.01m wstążki (czyli po 1cm). Dla 0 mamy bowiem wypisać "NIE".

Co nam dają te informacje. Mamy przedział odpowiedzi. Zobaczmy jaki może być maksymalny przedział. Wstążka może mieć do 1000m długości, a może być ich 10⁴. Maksymalna suma to zatem $10^7$. Na pewno musimy też przetworzyć każdą wstążkę. 10⁴ na pewno zmieści się w limicie czasu, ale musielibyśmy wykonywać stałą ilość operacji dla każdej z nich. Na liniową dla każdej nie możemy sobie pozwolić. Pozostaje nam logarytm. A co gdybyśmy wykonali logarytmiczną ilość operacji na tym właśnie przedziale? Mielibyśmy 24e7 operacji. Akceptowalne.

No ale co możemy zrobić z tym przedziałem? Możemy sprawdzać dla niektórych wartości czy da się uzyskać taki wynik. Jak? Wystarczy przejść wszystkie wstążki i podzielić każdą z nich przez ową wartość. Jeśli suma podłóg z owych ilorazów jest mniejsza od ilości osób, to wiemy, że nie da rady osiągnąć owego wyniku. Dlaczego to działa? $\left\lfloor\frac{długość \ wstążki}{sprawdzany \ wynik}\right\rfloor$ określa dla ilu osób starczy wstążki jeśli założy się, że to ona jest tą najkrótszą. Skoro obchodzi nas tylko ta najkrótsza wstążka to możemy równie dobrze rozdawać wszystkim najkrótsze wstążki. Będziemy więc pesymistycznie zakładać, że każdy otrzyma równie krótką wstążkę nie tracąc na poprawności, bo osoba z najkrótszą wstążką i tak by otrzymała taką samą, a pozostali nas nie obchodzą. A zatem wracając do algorytmu, mamy sobie długość z przedziału $\left(0; \ suma \ długości\right>$ i sprawdzamy dla każdej wstążki pomieści takich części. Suma tych części musi starczyć oczywiście dla wszystkich osób. Jeśli nie starczy, to zmniejszamy naszą sprawdzaną wartość. Jeśli starczy, to zwiększamy ją.

By uzyskać logarytmiczną ilość sprawdzonych długości, musimy poruszać się po przedziale wyszukiwaniem binarnym. A zatem, zaczynamy od przedziału $\left<0; \ suma\right>$ (0 też bierzemy pod uwagę - na końcu dopiero jeśli je otrzymamy, to wypiszemy "NIE") i sprawdzamy środkową wartość $\frac{suma}{2}$. Jeśli okaże się, że owa wartość nie starczy to zamieniamy przedział na $\left<0; \frac{suma}{2}\right)$. Jeśli jednak starczy to nasz nowy przedział to $\left<\frac{suma}{2}; \ suma\right>$ - nie wykluczamy $\frac{suma}{2}$ jak w poprzednim wypadku, gdyż jest to potencjalny wynik. Czynność powtarzamy, aż przedział będzie zawierał jedynie 2 jednostki. Sprawdzamy wtedy obie i mamy pewność, że nasz wynik jest optymalny.

Taka technika jest nazywana wyszukiwaniem binarnym po wyniku. Jak rozpoznać zadanie, w którym można ją zastosować? Otóż przede wszystkim mamy ograniczony przedział wyniku oraz jest to problem optymalizacyjny. Ostatnim kryterium jest możliwość szybkiego sprawdzenia czy dany wynik da się osiągnąć.

Złożoność: $O\left(n \cdot \log_2 \left(n \cdot r\right)\right)$, gdyż dla logarytmicznej ilości długości wstążek (wyszukiwanie binarne) sprawdzamy każdą wstążkę i w czasie stałym obliczamy ile osób ona zaspokoi ($r$ to maksymalna długość wstążki).

Algorytm:

int main()
{
        int n, m, s, i, a, b, c, in[10009];

        get(n,& m);
        for(b = i = 0; i < n; ++i)
                scanf("%d.%d", &a, &c), // wyjątkowo pokazane wczytanie (patrz poniższa linia)
                in[i] = a*100+c, // zamieniam liczbę rzeczywistą na naturalną, żeby łatwiej się liczyło
                b += in[i];
        b /= m; a = 0; // "a" to początek naszego przedziału, a "b" to koniec
        while(b-a > 1)
        {
                c = a+b>>1; // c to środek przedziału
                for(s = i = 0; i < n; ++i) // sprawdzamy ile osób pokryjemy danym kawałkiem
                        s += in[i]/c;
                if(s < m) // jeśli za mało
                        b = c-1;
                else // jeśli wystarczy nam kawałków
                        a = c;
        }
        s = 0;
        if(b) // jeżeli nie doszliśmy do przedziału 0..0
                for(i = 0; i < n; ++i) // sprawdź wynik dla b
                        s += in[i]/b;
        if(s >= m) // jeśli wystarczy to b z powrotem zamień b na liczbę rzeczywistą
                print(b/100.0);
        else if(!a) // jeśli a =0 to mamy przedział 0..0, więc wypisujemy NIE
                print("NIE"),
        else // inaczej a jest naszym wynikiem
                print(a/100.0);
}