Algoritmus
Néhány észrevételt teszünk.
- A futószalagok helye nem számít, csak a hossza, hiszen a futással megtett
út tetszőlegesen bontható kisebb szakaszokra. Tehát csak az számít, hogy milyen sebességű futószalagból összesen hány méter van. Ahol nincs szalag, azt tekinthetjük 0 sebességűnek.
-
A lassabb futószalagokon éri meg futni. Bizonyítás ötlet: legyen két szakaszon a sebesség $x>y$. Ekkor $\frac{1}{x}-\frac{1}{x+1}< \frac{1}{y}-\frac{1}{y+1}$, tehát a rövidebb futószalagon futva többet nyerünk időben.
Az előzőekből következik a megoldás alapsémája:
- Összegezzük az adott sebességgel megtehető szakaszok hosszát minden lehetséges sebességre.
- A kapott - összevont - szakaszokat rendezzük a szakaszon érvényes sebesség szerint.
- Eszerint a rendezés szerint haladva: amíg van még szuflánk és nem értünk célba, addig futunk, utána sétálunk.
- A rendezés helyettesíthető azzal, hogy minden lehetséges sebességre (ebből összesen 101-féle lehet) összegezzük az olyan sebességű szakaszok hosszát egy tömbben. Ekkor még a nulla osszú szakaszokat sem kell kihagyni, mert azok nulla másodperccel növelik az út idejét.
Kódok
