buldo

Algoritmul, pas cu pas

Buldozerul cară pământ doar spre dreapta. Cu lama fixată la $H$, fiecare zonă mai înaltă donează $h_i - H$ pe lamă, iar fiecare zonă mai joasă cere $H - h_i$. Singura condiție de respectat e ca, în orice moment, lama să aibă destul pământ pentru ce cere zona — adică încărcătura $C$ să nu scadă niciodată sub zero.

Întrebarea „care e cel mai mare $H$ fezabil” are o monotonie clară: cu $H$ mic e ușor (zonele cer puțin, donează mult), cu $H$ mare e greu. Asta ne-ar duce la o căutare binară pe $H$ — dar putem fi mult mai direcți dacă privim încărcătura $C$ ca o sumă de prefix.

Urmărește $C$ după fiecare zonă. Fiecare zonă, fie ea înaltă sau joasă, lasă în urmă exact $H$ (toate ajung la nivelul lamei). Deci după $i$ zone am „depus” în total $i \cdot H$, iar tot ce am adunat și nu am depus încă stă pe lamă:

$C_i = (h_1 + h_2 + \dots + h_i) - i \cdot H = \text{prefix}_i - i \cdot H.$