Answer these queries

23.02.2010 - Tomasz Górzny
TrudnośćTrudnośćTrudnośćTrudność

GSS2

Dla porządku:

  • $ A[1] \ldots A[N]; -100 000 \le A[i] \le 100 000 $- ciąg wejściowy
  • $ val(A[i] \ldots A[j]) = sum\{A[x] | i \le x \le j\} $ - suma po zbiorze

Przykład:

A = 4 -2 -2 3 -1
zapytanie (1,5) - val( 4, -2, -2, 3 ) = 4-2+3 = 5

Pora na ostatni i najtrudniejszy problem, czyli GSS2. Treść zadania jest prawie taka sama, jak pierwszego. Różnica polega na tym, że liczymy sumę różnych elementów. Największym błędem przy rozwiązywaniu jest za mocne sugerowanie się poprzednimi zadaniami. Tak naprawdę rozwiązuje się je podobnie, ale zupełnie inaczej. Na wstępie zauważmy, że możemy zapomnieć o sumach prefiksowych, bo problem nie ma takiej ładnej struktury. Zapominamy.

Oznaczanie powtórzeń

Zaczniemy od tego, że dla każdej pozycji wyznaczymy ostatni wcześniejszy indeks, pod którym znajduje się taka sama wartość (albo 0, jeżeli to pierwsze wystąpienie). Wartości ciągu A są małe, więc można (ale nie trzeba) zrobić to liniowo, w taki sposób:

1
2
3
for i = 1 .. N
  P[i] = last[ A[i] ]
  last[ A[i] ] = i
gdzie last to tablica o indeksach z zakresu [-100 000, 100 000] zainicjalizowana zerami. Jeśli wartość x jeszcze nie wystąpiła, to last[x] = 0, bo tak zostało zainicjalizowane. Jeżeli x wystąpiło, to przy ostatnim wystąpieniu w last[x] został zapisany odpowiedni indeks.

Liczymy val(A[1]..A[N])

Powiedzmy, że zapytanie jest jedno i szukana jest tylko wartość sumy. Postępujemy oczywiście tak, że dodajemy do siebie wartości z tych indeksów, które mają poprzednika ustawionego na 0. To było za proste :).

Ogólnie, dla zapytania (a,b) uwzględnimy tylko pola z poprzednikami mniejszymi od a (bo pozostałe już policzyliśmy).

1
2
3
4
wynik = 0
for i = a..b
  if P[i] < a
    wynik = wynik + A[i]

Komplikujemy - maksimum dla ustalonego jednego końca

Skomplikujmy: początek jest ustalony i trzeba znaleźć maksimum po końcach. Zapamiętujemy więc po drodze max z kolejnych wartości. Skomplikowaliśmy.

1
2
3
4
5
6
wynik = 0
maxWynik = 0
for i = a..b
  if P[i] < a
    wynik = wynik + A[i]
  maxWynik = max ( maxWynik, wynik )

Zamiast początku ustalmy koniec. Oczywiście zrobimy tak, że po prostu policzymy od końca (tzn odwracamy i liczymy normalnie). Nic przełomowego...

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
4.5
Twoja ocena: Brak Ocena: 4.5 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com