Wyszukiwanie binarne po wynikach cz I.

W części pierwszej przedstawię trzy zadania. Wszystkie zadanie można rozwiązać za pomocą metody zwanej wyszukiwaniem binarnym po wyniku. Oto i one:

Zadanie o krowach. Farmer John wybudował nową oborę dla krów z N boksami. Boksy są ulokowane w linii prostej na pozycjach x₁, x₂, ..., x_N. John ma C (C <= N) krów. Przy czym nie lubią one przebywać blisko ze sobą. Dlatego John chce tak umieścić krowy w boksach, aby odległość między dwoma najbliższymi krowami była możliwie jak największa.

Zadanie o złodzieju. Mamy dane n przedmiotów. Każdy przedmiot ma określoną cenę oraz określoną wagę. Złodziej chce ukraść i przedmiotów. Przy czym chce wybrać tak przedmioty, aby stosunek sumy cen wszystkich ukradzionych przedmiotów do sumy ich wag była jak największa. Należy podać wartość iloczynu z dokładnością dwóch cyfr po przecinku.

Zadanie o zabytkach. Mamy w mieście n zabytków. Chcemy je połączyć m jednokierunkowymi drogami. W każdym dniu będzie budowana jedna droga. Kolejność budowy dróg jest ustalona. Pytamy o najmniejsze takie k, że po k dniach będzie istnieć ścieżka zaczynająca się i kończąca przy tym samym zabytku.

Proponuję, aby Czytelnik spróbował samodzielnie rozwiązać każde z powyższych zadań. W tym miejscu nie ważna jest złożoność Twoich rozwiązań, ale docelowo będziemy chcieli, aby rozwiązania działały w czasie liniowo-logarytmicznym.

W II części wyjaśni się co te na pozór różne zadania mają ze sobą wspólnego.