Vrejuri

Fie Sm suma totala a vrejurilor la finalul celor K zile daca nu ar fi taiate. Trebuie ca in total sa scadem Sm - S din vrejuri. Pentru ca efortul depus pentru o operatie este patratul a cat taiem, trebuie sa incercam ca suma totala ce trebuie scazuta sa o impartim in taieri cat mai echilibrate (de exemplu daca vrem sa taiem un total de 7 in 3 operatii cel mai bine este 2, 2 si 3). Asadar fie xi totalul pe care vrem sa il taiem din planta i. Vrem ca suma toturor xi-urilor sa fie egala cu Sm - S si xi-ul maxim sa fie cat mai mic posibil. In acelasi timp vrem ca fiecare xi sa fie impartit in cele K zile cat mai echilibrat posibil.

Pentru aceasta putem cauta binar xi-ul maxim pe care il taiem. Fie q aceasta valoare. Din fiecare planta vom taia min( q, Hi + K * Pi ). Fie ST = suma dupa i=1,N din min( q, Hi + K * Pi ). Daca ST < Sm - S atunci q este prea mic. Daca ST > Sm - S atunci q este prea mare. Daca cele doua sunt egale atunci q este valoarea cautata si am descoperit xi = min( q, Hi + K * Pi ), cat taiem din fiecare planta. Tot ce ramane de facut este sa impartim fiecare xi in K valori cat mai egale. Vom avea K - xi mod K valori egale cu xi / K si xi mod K valori egale cu xi / K + 1 (exemplu de mai sus cu valoarea 7 impartita in 3 valori cat mai egale este concludenta). Costul total va fi suma patratelor fiecarei taieturi individuale.

Aceasta solutie are o complexitate N * log val_max, unde val_max este valoarea maxima pe care o poate atinge un vrej. O solutie N * log N se poate obtine daca sortam vrejurile dupa inaltimea finala la care ajung netaiate, si aflam q fara o cautare binara.