[SMWP_105] Respekt

0 Flares Twitter 0 Facebook 0 0 Flares ×

Link do zadania:
http://www.spoj.com/SMWP/problems/SMWP_105/

Opis problemu:
Jaś planuje dołączyć do grona najlepszych graczy. Warunkiem dołączenia do grupy jest pokonanie kilku losowych graczy. Jaś próbuje określić swoje szanse poprzez sprawdzenie ilu graczy posiada więcej krążków niż on. Wówczas liczba ta odzwierciedla listę osób z którymi Jaś będzie miał większe problemy podczas rozgrywek. Naszym zadaniem jest policzenie liczby osób, które mają więcej krążków niż Jaś.

Rozwiązanie:
Naiwnie możemy dla każdego zapytania sprawdzać każdorazowo wejściowy ciąg danych i zliczać ile wartości jest większych od danej liczby pokemonów Jasia. Jednakże spotka to się z komunikatem „TLE”. Co więc możemy zrobić, aby przyśpieszyć czas przeszukiwania ciągu? Możemy go posortować w czasie logarytmicznym, a następnie przeszukać, lecz nie wyraz po wyrazie, a metodą dziel i zwyciężaj. Dzięki temu znacznie zmniejszymy ilość porównywanych elementów. Stosujemy tutaj algorytm przeszukiwania binarnego przekształconego na wyszukiwanie ostatniego elementu zbioru o danej wartości.
Funkcja zwraca nam ostatnią pozycję, na której występuje liczba równa liczbie krążków Jasia. Tym samym wiemy, że wartości „na prawo” od tej liczby są większe. Naszą odpowiedzią jest wówczas liczba wszystkich graczy minus jeden, ponieważ elementy w tablicy liczymy od 0, odjąć pozycja wskazana przez funkcję.

Rozwiązanie sprytne:
Jeszcze łatwiej możemy to zadanie rozwiązać używając zamiast przeszukiwania binarnego gotowej funkcji upper_bound(first,last,valuable), która działa w identyczny sposób wyznaczając nam ostatni element zbioru o danej wartości.

Uwaga! Samo zastosowanie przeszukiwania binarnego na posortowanym ciągu a następnie iterowanie do momentu napotkania większej wartości spotka się również z komunikatem „TLE”.

Print Friendly

Dodaj komentarz

Wymagane pola są oznaczone *.