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\ge c_2\ge \dots \ge 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\le s_i$ oraz próbujemy skonstruować najtańsze rozwiązanie, to możemy założyć, że $b_j\le b_i$. Możemy to udowodnić przez sprzeczność:

• W początkowym przypisaniu mieliśmy $s_i\le b_i$ i $s_j\le b_j$. Załóżmy, że $s_j\le s_i$ oraz $b_i<b_j$. Wtedy $s_i<b_j$ (jako że $s_i\le b_i<b_j$) i $s_j\le b_i$ (gdyż $s_j\le s_i\le 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\ge c_i$) wynika, że $(b_j-s_i)c_i+(b_i-s_j)c_j\ge (b_i-s_i)c_i+(b_j-s_j)c_j$. Faktycznie, możemy najpierw wszystko wymnożyć:
  $b_j{c}_i-s_i{c}_i+b_i{c}_j-s_j{c}_j\ge b_i{c}_i-s_i{c}_i+b_j{c}_j-s_j{c}_j$,
  następnie usunąć te same składniki:
  $b_j{c}_i+b_i{c}_j\ge b_i{c}_i+b_j{c}_j$,
  poprzenosić składniki:
  $b_i{c}_j-b_j{c}_j\ge b_i{c}_i-b_j{c}_i$,
  i wyciągnąć przed nawias:
  $(b_i-b_j)c_j\ge (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\le 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 $\mathtt{\text{std::multiset}}$ z STL oraz operacji $\mathtt{\text{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})\le 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}\le b_{k,j}$. W kolejnych miesiącach możemy dalej zachować taką nierówność, więc finalnie otrzymamy $b_{m,i}\le 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.