# 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]))
```