natatie

Algoritmul, pas cu pas

Gândește invers. În loc să întrebi „care e cea mai bună aranjare?", întreabă: dacă mi-aș permite o durată $T$, aș reuși să acopăr toate culoarele? Asta e mult mai ușor de verificat — și ne lasă să ghicim durata și să o rafinăm, în loc să o construim din nimic.

Rața de pe culoarul $j$ parcurge $2 d_j$, deci durează $2 d_j / v$. Durata cursei e cel mai mare dintre acești timpi. Cu cât $T$ e mai mare, cu atât e mai ușor să acoperi totul — deci putem căuta binar cea mai mică $T$ care încă funcționează.