New answers tagged


The greedy strategy works in this case (fill up as much as you need to reach the next cheaper city, or fill up to K if no cheaper city is reachable with a full tank). The proof is pretty much the same as most standard proofs for greedy algorithms: Among all optimal solutions, take the one that "agrees with the greedy strategy the longest" and show that this ...

Top 50 recent answers are included