Omówienie zadania Liczniki (II etap XXXI OI)

Uproszczenie

Dla ułatwienia najpierw będziemy rozważać sytuację, gdy mamy tylko \(m = 1\) miesiąc.

Już dla niej optymalne rozwiązanie jest nieoczywiste, dlatego skupiamy się najpierw na tym przypadku, aby dowiedzieć się czegoś więcej o strukturze całego zadania.

Dla przypomnienia, \(c_i\) oznaczało koszt bajtometra sześciennego wody na \(i\)-tym liczniku, a \(s_i\) początkową ilość zarejestrowanej wody. Oznaczmy przez \(a\) ciąg (multizbiór) odczytów po pierwszym miesiącu.

Sortowanie

Możemy sobie wyobrazić taki schemat rozwiązania, w którym w jakiejś kolejności bierzemy liczniki i przydzielamy im jeszcze niewykorzystane wartości z \(a\). Warto zadać sobie w takim momencie pytanie: W jakiej kolejności?

Często ustalenie dobrej kolejności danych jest kluczowe do rozwiązania problemu i bardzo często możemy to zrobić, ponieważ jest to czynność po naszej stronie. Gdy szukamy takiej kolejności, trzeba się zawsze zastanowić jakich własności mniej więcej oczekujemy i jakie własności mają kolejności, które rozważamy.

Możemy posortować nasze dane na wiele sposobów, między innymi, według \(a\) rosnąco/malejąco lub \(s\) rosnąco/malejąco lub \(c\) rosnąco/malejąco. Każda z nich ma swoje własności i czasem trzeba przyjrzeć się każdej kolejności, aby podjąć dobrą decyzję.

Intuicja

W przypadku tego zadania, intuicyjne jest takie podejście, że chcemy licznikom z dużym \(c_i\) przydzielić jak najmniejsze wartości liczników w kolejnym miesiącu. Zgodnie z tą intuicją możemy chcieć posortować liczniki po wartości \(c\).

Wspomnimy tutaj, że sortując po \(c\) niemalejąco, jesteśmy w stanie dociągnąć rozwiązanie do końca, ale jest to bardziej wymagające. Zachęcamy do zastanowienia się nad tym, ale nie jest to konieczne do zrozumienia rozwiązania wzorcowego.

Zatem, wracając na trop rozwiązania wzorcowego, będziemy sortować nierosnąco po \(c\). Przyjmiemy od tego momentu, że przenumerowujemy liczniki tak, aby spełniały \(c_1 \geq c_2 \geq \ldots \geq c_n\). Zbadajmy własności takiego sortowania. Załóżmy, że przydzieliliśmy już wartości wszystkim licznikom w pierwszym miesiącu i oznaczyliśmy te wartości ciągiem \(b_i\). Weźmy \(i\)-ty licznik. Mamy teraz kluczową własność, że dla każdego \(j < i\), jeżeli \(s_j \leq s_i\) oraz próbujemy skonstruować najtańsze rozwiązanie, to możemy założyć, że \(b_j \leq b_i\). Możemy to udowodnić przez sprzeczność:

• W początkowym przypisaniu mieliśmy \(s_i \leq b_i\) i \(s_j \leq b_j\). Załóżmy, że \(s_j \leq s_i\) oraz \(b_i < b_j\). Wtedy \(s_i < b_j\) (jako że \(s_i \leq b_i < b_j\)) i \(s_j \leq b_i\) (gdyż \(s_j \leq s_i \leq b_i\)), więc możemy zamienić \(b_i\) oraz \(b_j\) ze sobą. Wynikiem z tych dwóch liczników w pierwszym przypadku było \((b_i - s_i)c_i + (b_j - s_j)c_j\), a po zamianie będzie \((b_j - s_i)c_i + (b_i - s_j)c_j\). Z posiadanych założeń (koniecznym jest \(c_j \geq c_i\)) wynika, że \((b_j - s_i)c_i + (b_i - s_j)c_j \geq (b_i - s_i)c_i + (b_j - s_j)c_j\). Faktycznie, możemy najpierw wszystko wymnożyć:
  \(b_jc_i - s_ic_i + b_ic_j - s_jc_j \geq b_ic_i - s_ic_i + b_jc_j - s_jc_j\),
  następnie usunąć te same składniki:
  \(b_jc_i + b_ic_j \geq b_ic_i + b_jc_j\),
  poprzenosić składniki:
  \(b_ic_j - b_jc_j \geq b_ic_i - b_jc_i\),
  i wyciągnąć przed nawias:
  \((b_i - b_j)c_j \geq (b_i - b_j)c_i\). I już.

Rozwiązanie

Na podstawie powyższego argumentu z zamianą możemy wysnuć takie podejście, że będziemy przeglądać liczniki nierosnąco po \(c_i\) oraz przydzielać im najmniejsze \(b_i\) spełniające \(s_i \leq b_i\). To rozwiązanie jest optymalne, ponieważ każde inne przypisanie możemy sprowadzić takimi zamianami do przypisania, które wyprodukuje ten algorytm (nie pogarszając po drodze wyniku). To jest bardzo silna własność, dzięki której stwierdzamy też, że jeżeli jakiekolwiek przypisanie istnieje, to nasz algorytm je znajdzie.

Do implementacji tego rozwiązania w C++ możemy użyć struktury \(\texttt{std::multiset}\) z STL oraz operacji \(\texttt{lower_bound}\) na niej.

Dowolne \(m\)

Rozwiązanie dla dowolnego \(m\) jest uogólnieniem rozwiązania dla \(m = 1\). Poprawnie jest zastosować algorytm dla \(m = 1\) po prostu \(m\) razy tak, jakby każdy kolejny miesiąc był tym ostatnim miesiącem.

Dowód poprawności jest tak na prawdę uogólnieniem argumentu, który użyliśmy wcześniej. Weźmy jakieś przypisanie liczników, które oznaczymy jako \(b_{i, j}\), gdzie \(i\) to numer miesiąca, a \(j\) to numer licznika. Teraz bierzemy dowolne dwie pozycje \(i < j\) i szukamy miesiąca \(k\) takiego, że \(\max(b_{k - 1, i}, b_{k - 1, j}) \leq \min(b_{k, i}, b_{k, j})\). Możemy ustawić dowolnie odczyty na tych licznikach w \(k\)-tym miesiącu, więc ustawimy je tak, aby spełnione było \(b_{k, i} \leq b_{k, j}\). W kolejnych miesiącach możemy dalej zachować taką nierówność, więc finalnie otrzymamy \(b_{m, i} \leq b_{m, j}\). Jeśli takie \(k\) nie istniało, to nic nie robimy. Wykonując taką zamianę, nie mogliśmy pogorszyć wyniku. Za pomocą tej zamiany możemy sprowadzić każde przypisanie do tego, które oblicza nasz algorytm, więc nasz algorytm jest optymalny.