Zadanie Szczyty

Question

Cześć mam takie zadanie

Mateusz pakuje się na wyprawę do Gór Bajtockich. Ma już mapę trasy, po której będzie się poruszał. Jest to n kolejnych miejsc położonych na pewnych wysokościach. Szczytem nazwiemy miejsce, dla którego dwa sąsiednie miejsca są niżej położone. Zakładamy, że pierwsze i ostatnie miejsce nie jest szczytem. Mateusz chce podzielić całą trasę na spójne odcinki o takiej samej liczbie miejsc. W każdym odcinku chciałby ustawić dokładnie jedną flagę. Postanowił, że flagi może rozmieszczać tylko na szczytach. Pomóż Mateuszowi i oblicz, ile maksymalnie flag będzie mógł rozmieścić.

Wejście W pierwszym wierszu wejścia jest jedna liczba całkowita n (1 <= n <= 500 000) oznaczająca liczbę miejsc na trasie. Kolejny wiersz wejścia zawiera n liczb całkowitych t0, t1, . . . , tn−1 (1 <= ti <= 109 ), gdzie ti oznacza wysokość i-tego miejsca. Wyjście Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą równą maksymalnej liczbie flag, które może rozmieścić Mateusz.

MOJ KOD

Tutaj sprawdzam poprawność

Pomoże mi ktoś znaleźć błąd ? :D

Answer 1

Masz błąd w implementacji tablicy sum prefiksowych. Jej rozmiar powinien wynosić n+1, a nie n. I teraz suma elementów od indeksu 0 do indeksu i znajduje się w tablicy pref pod indeksem i+1, a nie pod indeksem i.

Czyli w pętli w której obliczasz tablicę pref musisz zamienić:

pref[i] = pref[i-1] + 1;

na:

pref[i+1] = pref[i] + 1;

Analogicznie musisz poprawić linię 7,  22, 24. Z czego linię 7 zamieniasz na to:

if (pref[i+dz] - pref[i] < 1) return false; 

Comments

Mógbyś wytłumaczyć mi dlaczego wcześniejsze tworzenie tablicy pref było błędne ? dlaczego musi być ta pierwsza zerowa wartość ?

---

Ogólnie istnieją dwie metody tworzenia tablicy sume prefiskowych. W piewszej sumę na przedziale [l, r] liczy się wzorem pref[r+1]-pref[l], a w drugiej wzorem pref[r]-pref[l-1]. Ja akurat wybrałem tę pierwszą wersję.

W pierwszej wersji pref[i+1] oznacza sumę elementów o indeksach 0...i. I teraz jeżeli chcesz obliczyć sumę na przedziale [l, r] to wiemy, że pref[r+1] zawiera sumę elementów od 0 do r, a pref[l] zawiera sumę elemntów od 0 do l-1. No a dlaczego pref[l] a nie pref[l+1]? Bo żeby obliczyć sumę na przedziale [l, r] musisz od sumy elementów od 0 do r odjąć sumę elementów od 0 do jednego wcześniej niż l, czyli l-1.

I teraz gdybyś chciał liczyć sumę elementów od indeksu 0 do indeksu 0 to znowu musisz odjąć od sumy elemntów [0, 0] sumę elemntów od 0 do jeden przed 0, tylko że taki indeks nie istnieje. Dlatego musimy wymusić takie przesunięcię, w którym suma na przedziale [0, i] znajduje się w pref[i+1] i dzięki temu pref[0] zawiera ten indeks o jeden przed 0.