Divide and conquer algorithm for a gas station problem

Question

I never heard about this variation of the gas station problem. The statement is as follows:

There is just one road connecting the n+1 cities c0, …, cn consecutively. You want to go from c0 to cn stopping at most s times to fill the tank of the car. There are gas stations at the cities, but none on the roads. The length of each road is ℓ0, …, ℓn−1. Which is the minimum range for your car? Suppose that you start with a full tank.

This has to be done in something like nlogn, because I already tried the n^2 approach and is not good. I don't know how to decide if I should refill at some point or not. For this inp:

5 0
100 300 500 200 400
5 1
100 300 500 200 400
5 2
100 300 500 200 400
5 3
100 300 500 200 400
5 4
100 300 500 200 400

The output should be: 1500 900 600 500 500

(Consider that the input is a sequence of n and s, followed by n naturals that represents l_i.

Source

Answer 1

You can use binary search on the range of the car. Refill only if needed.

---

Here is the algorithm in more detail.

1. Let low = 0 and high = distance from c0 to cn. During the whole algorithm, range high is always big enough for a car to reach cn from c0, while range low is always not.
2. Repeat the following as long as low + 1 < high
   1. mid = (low + high) /2
   2. If range mid is big enough, set high = mid. Otherwise, set low = mid.
3. Return high, which must be the minimum range of the car.

---

How can we check if a given range is big enough?

Simple.

We will try driving a car with that range from c0 to cn. At each city, if the remaining range of the car is not enough for the car to reach the next city, refill the car to its full range. If we have refilled s+1 times before we have reached cn, that given range is not enough. Otherwise, it is enough.

---

It takes $O(n)$ time to check whether a given range is big enough.
The bisecting loop will run at most $\lceil\log_2 m\rceil$ iterations, where $m$ is the distance from c0 to cn.
So, the algorithm runs in $O(n\log_2 m)$-time.