Łapanie Wody

Zadanie

Wzdłuż ściany zostały ułożone klocki. Następnie na klocki nałożono przezroczystą ściankę. Pojemnik po bokach jest otwarty. Zaczęto nalewać wodę do środka. Ile wody zostanie uwięzione przez klocki? Zakładamy, że każdy klocek jest sześcianem i ma objętość 1 litra.

Przykład

Na wejściu dana jest lista, która określa ile jest klocków w każdej kolejnej kolumnie. Wszystkie wartości liczbowe są nieujemne. Oto przykładowa ilustracja dla listy {0, 3, 1, 1, 4, 1, 0, 2, 0}.

Ilustracja przykładu

Przedstawiona konstrukcja może pomieścić 7 litrów. Pierwsza i ostatnia kolumna nie zatrzymuje żadnej wody, ponieważ z jednej strony nie ma nic co by zatrzymało wodę. Pomiędzy kolumną o wysokości 3 i 4 zmieszczą się 4l, ponieważ najwyższa wysokość wody to 3. Z kolei po prawej stronie najwyższej kolumny maksymalny poziom wody to 2.

Implementacja

Rozwiązanie Podstawowe

Podstawowy sposób obliczenia ile wody zostanie w konstrukcji polega na wybraniu każdej kolejnej kolumny i sprawdzeniu co ogranicza je z lewej i prawe strony. Do tego przyda się specjalna funkcja maksimum(), która sprawdzi elementy z określonego zakresu. Przyjmujemy, że wysokość poza ścianką to 0. Oto kod funkcji:

1. int maksimum(vector<int> lista, int poczatek, int koniec) {
2.   if (poczatek < 0 || poczatek >= lista.size() || poczatek > koniec)
3.     return 0;
4.   int max = 0;
5.   while (poczatek < koniec) {
6.     if (lista[poczatek] > max) {
7.       max = lista[poczatek];
8.     }
9.     poczatek++;
10.   }
11.   return max;
12. }

Teraz można przejść do napisania głównej funkcji ileWody(), która dla każdego kolumny klocków wyszukuje ograniczenie na lewo i prawo, a następnie na podstawie uzyskanych ograniczeń i wysokości danej kolumny określa czy zostanie tam nalana jakakolwiek woda. Tutaj należy pamiętać, że ograniczenie minus wysokość danej kolumny może być ujemna. Wtedy należy nie dodawać do łącznej ilości zatrzymanej wody.

1. int ileWody(vector<int> lista) {
2.   int lacznie = 0;
3.   for (int i = 0; i < lista.size(); i++) {
4.     int lewo = maksimum(lista, 0, i);
5.     int prawo = maksimum(lista, i + 1, lista.size());
6.     int min = lewo < prawo ? lewo : prawo;
7.     int dodaj = min - lista[i];
8.     if (dodaj > 0)
9.       lacznie += dodaj;
10.   }
11.   return lacznie;
12. }

Zauważmy, że takie rozwiązanie wymaga przejrzenia całej tablicy za każdym razem, gdy sprawdzana jest kolejna kolumna. Jeśli oznaczymy przez n długość tablicy to dla n elementów jest wykonywane n - 1 porównań elementów - algorytm ma w takim razie złożoność kwadratową O(nn²).

Rozwiązanie Optymalne

Złożoność algorytmu można poprawić do liniowej O(n) poprzez utworzenie tablic pomocniczych, gdzie na początku algorytmu zostanie zapisane jak wysoka do tej pory została kolumna dla danego indeksu patrząc od lewej oraz patrząc od prawej strony. Następnie przeglądając elementy zamiast wyznaczać wartości można je od razu odczytać i dopisać odpowiednią wartość.

1. int ileWody(vector<int> lista) {
2.   int n = lista.size();
3.   int * odLewej = new int[n];
4.   odLewej[0] = lista[0];
5.   for (int i = 1; i < n; i++)
6.     odLewej[i] = max(odLewej[i - 1], lista[i]);
8.   int * odPrawej = new int[n];
9.   odPrawej[n - 1] = lista[n - 1];
10.   for (int i = n - 2; i >= 0; i--)
11.     odPrawej[i] = max(odPrawej[i + 1], lista[i]);
13.   int lacznie = 0;
14.   for (int i = 0; i < n; i++)
15.     lacznie += min(odLewej[i], odPrawej[i]) - lista[i];
17.   delete[] odLewej, odPrawej;
18.   return lacznie;
19. }

Testowanie funkcji

W celu wczytania listy liczb, aby przetestować działanie funkcji wystarczy poniższy fragment kodu:

1. int main() {
2.   int n, t;
3.   cout << "Ile elementow\n n = ";
4.   cin >> n;
5.   cout << "Podaj elementy:" << endl;
6.   vector<int> lista;
7.   while (n--) {
8.     cin >> t;
9.     lista.push_back(t);
10.   }
11.   cout << "Pomiesci sie " << ileWody(lista);
12.   system("pause");
13.   return 0;
14. }

• Kod źródłowy Implementacja