Hints : Line Trip

Assume that there’s only one gas station located at point a. What is the the minimum volume of gas tank needed?

0 <--> a <--> x

If there’s a single station located at a, you need to ensure that:

• You safely reach from point 0 to point a. Hence, you need a capacity of atleast (a - 0).
• You safely reach point x. But notice that there’s no gas station at point x, so with the same fuel, you need to come back to point a again. Hence, we need at least 2 * (x - a) capacity.
• Finally, you also need to reach point 0 from point a. This has a contribution of (a - 0), which is already counted in the first step.

Hence, minimum total capacity: max((a - 0), 2(x - a)).

Now, assume that there are 2 gas stations located at points a and b (in the same order). What is the the minimum volume of gas tank needed?

0 <---> a <---> b <---> x

With 2 stations, you need to ensure that:

• You safely reach from point 0 to point a. Hence, you need at least (a - 0).
• You safely reach from point a to point b. Hence, you need at least (b - a).
• You safely reach point x. But notice that there’s no gas station at point x, so with the same fuel, you need to come back to point b again. Hence, we need at least 2 * (x - b) capacity.
• Next, you need to reach point a from point b. This has a contribution of (b - a) which is already included in step 2.
• Finally, you also need to reach point 0 from point a. This has a contribution of (a - 0), which is already counted in the first step.

Hence, minimum total capacity: max((a - 0), (b - a), 2(x - a)).

With n stations, the minimum total cost capacity is

max((a[0] - 0), (a[1] - a[0]), ..., (a[n - 1] - a[n - 2]), 2(x - a[n - 1]))