Karen and Coffee – omówienie

Treść zadania

https://codeforces.com/problemset/problem/816/B

O co chodzi w zadaniu?

Dostajemy liczbę n, k i q oznaczające liczbę recept, minimalną liczbę recept żeby temperatura była zarekomendowana, oraz liczbę zapytań. Po wczytaniu tych trzech liczb otrzymujemy n recept i q par przedziałów temperatur. Naszym zadaniem jest wypisanie dla każdego przedziału liczby temperatur których ilość w receptach jest >= k.

Jak się za to zabrać?

Załóżmy, że mamy dostęp w czasie stałym do liczby poprawnych recept w danym przedziale, wtedy nasz problem problem stałby się prosty, gdyż wczytując przedziały wystarczyłoby wypisać naszą liczbę w czasie stałym.

Jednak jak stworzyć taką strukturę danych z wcześniej podanych liczb?

Otóż mamy dwa potężne narzędzia, które pomogą nam w rozwiązaniu tego problemu, są to sumy prefiksowe i zliczanie elementów.

Tak więc najpierw analizujemy wszystkie recepty, na przykład dla recepty o sugerującej temperatury na przedziale:  [2, 5] musimy zwiększyć tab[2] o jeden i zmniejszyć tab[6] o jeden, gdyż dzięki tak zainicjowanej tablicy możemy uzupełnić ją liniowo dodając do każdej komórki poprzednią wartość. Dla wartości:

1 3

4 5

5 6

3 9

Otrzymamy:

0 1 0  0 1 1 -1 -1 0 0  -1 0 – Wartość

0 1 2  3 4 5 6  7 8 9 10 11 – Indeks

A po policzeniu sum prefiksowych:

0 1 1 1 2 3 2 1 1 1   0 0 – Wartość

0 1 2 3 4 5 6 7 8 9 10 11 – Indeks

Gdy już to zrobimy nasze rozwiązanie jest prawie gotowe, gdyż w czasie liniowym potrafimy znaleźć odpowiedź dla dowolnego przedziału.

Jednak nie jest to czas stały więc dla wielu przedziałów wciąż będziemy mieli złożoność kwadratową. Dlatego też musimy stworzyć tablice sum prefiksowych, dzięki której wyznaczenie wartości w dowolnym przedziale będzie się odbywało w czasie stałym, a całe rozwiązanie w liniowym.

Tak więc mając powyższą tablicę tworzymy nową tablicę (bądź zapełniamy tą) zerami i jedynkami, w następujący sposób:

Jeśli wartość w tablicy o indeksie i jest >= k to zapisujemy w nowej tablicy jeden, w przeciwnym wypadku zero.

Dla takiego przykładu:

4 2 2

1 3

4 5

5 6

3 9

4 6

8 10

Nasza tablica będzie zmieniać się następująco:

0 0 0 0 0 0 0 0 0 0   0 0 – Wartość

0 1 2 3 4 5 6 7 8 9 10 11 – Indeks

Uzupełnianie tablicy jedynkami i minus jedynkami:

0 1 0  0 1 1 -1 -1  0 0 -1 0 – Wartość

0 1 2  3 4 5 6  7 8 9 10 11 – Indeks

Liczenie sum prefiksowych:

0 1 1 1 2 3 2 1 1 1  0 0 – Wartość

0 1 2 3 4 5 6 7 8 9 10 11 – Indeks

k = 2, więc dla każdej liczby >= 2  zapisujemy 1, a dla niższych 0

0 0 0 0 1 1 1 0 0 0  0 0 – Wartość

0 1 2 3 4 5 6 7 8 9 10 11 – Indeks

Liczenie sum prefiksowych:

0 0 0 0 1 2 3 3 3 3  3 3 – Wartość

0 1 2 3 4 5 6 7 8 9 10 11 – Indeks

Więc naszym wynikiem będzie:

3

0

Gdyż dla przedziału 4 6 tab[6] – tab[4-1] = tab[6] – tab[3] = 3 – 0 = 3,

oraz dla przedziału 8 10 tab[10] – tab[8-1] = tab[10] – tab[7] = 3 – 3 = 0

Link do kodu

https://ideone.com/jT7Oku

Autor: Michał Woźniak

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

*