[SMWP_112] Rozkład Pracy

0 Flares Twitter 0 Facebook 0 0 Flares ×

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

Omówienie:

Tworzymy mapę i wrzucamy każdy początek i koniec, który wystąpił w podanych przedziałach.
Przypisujemy każdej z tych liczb wartość 0. Sortujemy przedziały niemalejąco względem końca.
Po posortowaniu sprawdzamy każdy przedział następująco:
-szukamy na mapie liczby mniejszej od początku przedziału – pomocnicza
-jeżeli wartość dla końca przedziału na mapie jest mniejsza od sumy wartości pomocniczej na mapie i kwoty pieniędzy , to uaktualniamy ją.

Wynikiem jest wartość z mapy dla największego końca.

Print Friendly

1 Komentarz

  1. Rozwiązanie alternatywne.
    Sortujemy względem początków (niemalejąco). Następnie przechodzimy przez kolejne elementy wrzucając je do kolejki priorytetowej (priorytet definiujemy względem końców – im mniejsza wartość końca tym wyższy priorytet elementu). W jaki sposób modyfikujemy wrzucane do kolejki elementy? Dla każdego elementu sprawdzamy, które elementy z kolejki mają mniejsze wartości końców od początku badanego elementu – usuwamy je z kolejki i wstawiamy tylko jeden z maksymalną płacą do tej pory. Do kolejki wrzucamy element powiększony o tą znalezioną maksymalną wartość.

Dodaj komentarz

Wymagane pola są oznaczone *.