Omówienie zadania Pojemniki (II etap XXXI OI)

Jeżeli suma ilości substancji przekracza sumaryczne dostępne miejsce w pojemnikach (wynoszące \(n\cdot k\)), to na pewno nie można zmieścić wszystkich substancji w pojemnikach, więc odpowiedzią jest "NIE". Od teraz w rozwiązaniu zakładamy, że ta suma jest nie większa niż \(n\cdot k\).

Intuicja

W pierwszej kolejności można spróbować przypisać substancje do pojemników w taki sposób, aby jak najwięcej pojemników posiadało parę substancji, których ilość sumuje się do \(k\). Takie podejście ma na celu zminimalizowanie nieużytego miejsca w pojemnikach (ale jeszcze nie wiemy, czy takie podejście jest optymalne). Żeby osiągnąć taką sytuację, naturalne wydaje się być łączenie substancji o małej ilości bajtolitrów z substancjami o dużej ilości bajtolitrów. Można wtedy spróbować zastosować podejście polegające na przypisaniu substancji mającej mało bajtolitrów do pojemnika razem z substancją, której jest co najmniej tyle bajtolitrów, że razem w pełni zapełniają ten pojemnik.

Kluczowy pomysł

Gdy w pojemniku umieszczamy pewną substancję, której jest \(a_i \leq k\), to możemy dopełnić ten podejmij dowolną inną (o ile istnieje) substancją, której jest \(a_j > k\) (i wtedy jeszcze trochę zostanie tej drugiej substancji). W ten sposób sprowadzamy problem do sytuacji, w której mamy jeden pojemnik mniej, jedną substancję mniej (tę pierwszą zużyliśmy całą) oraz sumę ilości substancji mniejszą o dokładnie \(k\), więc w szczególności pozostała suma ilości substancji dalej nie przekracza sumy rozmiarów pojemników.

Rozwiązanie

W większości przypadków uda nam się znaleźć pewną parę substancji taką, że jednej jest co najwyżej \(k\) bajtolitrów, a drugiej więcej niż \(k\) bajtolitrów. Gdybyśmy nie byli w stanie znaleźć takiej pary, to zachodziłby jeden z dwóch przypadków:

• Każdej substancji jest co najwyżej \(k\) bajtolitrów, a wtedy możemy każdą z nich przypisać do osobnego pojemnika.
• Każdej substancji jest więcej niż \(k\) bajtolitrów, a wtedy suma ilości przekracza sumę rozmiarów, co sprawdziliśmy już wcześniej, więc taki przypadek nie może wystąpić.

Daje to następujący zarys poprawnego rozwiązania, który wykonuje liniowo wiele kroków:

• sprawdź, czy istnieje para substancji, z których jednej jest co najwyżej \(k\) bajtolitrów, a drugiej jest więcej niż \(k\) bajtolitrów,
• jeżeli taka para istnieje, to w jednym pojemniku umieść całą ilość pierwszej substancji i możliwie dużo drugiej, co redukuje problem do instancji z mniejszą liczbą pojemników i substancji,
• jeżeli taka para nie istnieje, to przypisz każdą substancję do osobnego pojemnika i zakończ działanie algorytmu.

 

Implementacja

Możemy skorzystać ze struktury set w języku C++. Ta struktura utrzymuje posortowany zbiór elementów. Będziemy w niej utrzymywać pary \(<\)pozostała ilość substancji, numer substancji\(>\), które porównujemy na podstawie ilości (lub leksykograficznie). Aby wykonać jeden krok rozwiązania, można wybrać najmniejszy oraz największy element ze struktury. Takie rozwiązanie ma złożoność czasową \(O(n\log{n})\) i pamięciową \(O(n)\).

Implementacja liniowa

Istnieje również rozwiązanie liniowe. Będziemy utrzymywać dwa zbiory. W jednym z nich będą znajdować się substancje, których ilość nie przekracza \(k\), a w drugim pozostałe substancje. Operacje, które musimy umieć wykonywać na tych zbiorach, to wyjęcie dowolnego elementu ze struktury oraz dodanie elementu do struktury. Tym razem, żeby wykonać jeden krok rozwiązania, wystarczy wybrać po jednym dowolnym elemencie (w szczególności, można wybrać ostatnie elementy) z obu zbiorów. Być może w pewnym momencie trzeba będzie przerzucić tak wybrany element z jednego zbioru do innego, ale to także można wykonać takimi operacjami. Potrzebna struktura danych to taki worek z elementami. Do jego implementacji możemy wykorzystać właściwie dowolną strukturę do przechowywania kolekcji danych w języku C++, np. strukturę vector. Operację wyjęcia (ostatniego) elementu można zrealizować poprzez funkcję pop_back, a dodanie elementu poprzez emplace_back. Złożoność wychodzi \(O(n)\).