1126. Buying Fuel at the Right Price

A van drives from kilometre 0 to kilometre D, burning one litre per kilometre. Its tank holds C litres and starts EMPTY.

There are n stations at strictly increasing positions, the first of them at kilometre 0. Station i sells fuel at price per litre and you may buy any whole number of litres there, as long as the tank never holds more than C. Consecutive stations are at most C apart and the last station is at most C from D, so the drive is always possible.

Print the least total cost of reaching D.

D = 10, C = 4, stations (0, price 5) (3, price 2) (7, price 4) -> 35 D = 5, C = 5, station (0, price 3) -> 15 D = 10, C = 5, stations (0,1) (5,9) (9,9) -> 50

Trace the first line. At kilometre 0 the price is 5 and the next station is 3 kilometres away at a price of 2, which is cheaper, so buy exactly 3 litres for 15. At kilometre 3 the price is 2 and nothing within the 4-kilometre range is cheaper, so fill the tank: 4 litres for 8, which carries the van to kilometre 7. At kilometre 7 the price is 4 and D is 3 kilometres away, which is within range, so buy exactly 3 litres for 12. The total is 15 + 8 + 12 = 35.

## What most people try first

Filling the tank at every station. On the first example that buys 4 litres at 5, then refills at 3 and at 7, and ends up carrying fuel bought expensively past cheaper stations. It costs more than 35.

Buying only just enough to reach the next station. On the third example the first station is the cheapest of all, and buying only 5 litres there means paying 9 per litre later, for a total of 5 + 45 = 50, which happens to match because the tank cannot hold more than 5 anyway; change C to 10 and the just-enough rule pays 5 + 45 = 50 while filling up at the cheap station pays 10.

Building a table over (station, litres in tank) is exact and costs O(n * C), which with C up to 10^9 is not a table anyone can hold.

## The method

At each station, look ahead as far as the tank allows.

for every station i, find nxt[i] = the next station with a STRICTLY LOWER price (a decreasing-price stack does this in one backward pass) fuel = 0 cost = 0 for i from 0 to n-1: j = nxt[i] if j exists and pos[j] - pos[i] <= C: need = pos[j] - pos[i] # just enough to reach the cheaper station else: need = min(C, D - pos[i]) # fill the tank, or just enough to finish if need > fuel: cost = cost + (need - fuel) * price[i] fuel = need drive to the next station or to D, subtracting the distance from fuel print cost

One backward pass for the stack and one forward pass for the driving, so O(n).

## Why it is correct

Every litre burned between two kilometres was bought at some station at or before the first of them. The cost is therefore the sum over litres of the price of wherever that litre was bought, and the greedy is claiming that each litre is bought at the cheapest station from which it could possibly have been bought given the tank.

Consider the first station i at which an optimal plan and the greedy differ in how much they buy.

If the greedy buys LESS, it is because a strictly cheaper station j is within range. Any litre the optimal plan buys at i beyond what is needed to reach j is still in the tank at j, so move that purchase from i to j. The tank constraint still holds, because the tank holds less at every point between i and j and the same amount from j onward, and the cost strictly falls since price[j] < price[i]. So no optimal plan buys more than that at i.

If the greedy buys MORE, it is because no cheaper station is in range, so every station the van can reach from i sells at price[i] or above. Any litre the optimal plan buys later instead can be bought at i for no more, and moving the purchase earlier keeps the tank within C, because the greedy's purchase itself never exceeds C. So the greedy's larger purchase is no worse.

Either way the greedy's choice at the earliest disagreement can be swapped into an optimal plan without raising the cost, which is the exchange argument.

## The boundary that breaks a careless implementation

The look-ahead must be for a STRICTLY lower price. Using "lower or equal" makes the van buy just enough to reach an equally priced station, which costs the same and is harmless, but the stack that finds the next such station then behaves differently on plateaus and is easy to get wrong; strict is the version to write.

The last leg is D - pos[i], not C. Filling the tank at the final station and driving off with fuel left over pays for litres that are never burned.

The distance test is pos[j] - pos[i] <= C, with <=. A cheaper station exactly a tankful away is reachable.

## Sizes

D reaches 10^9 and a price reaches 10^6, so the cost reaches 10^15. That is far past the 2147483647 limit of a signed 32-bit integer, and the last test drives four thousand kilometres at a million per litre for a cost just under 4 * 10^9.

## A related problem

Problem #761 asks for the smallest TANK that survives a drive within a stop budget, and its greedy is "always drive to the furthest station in reach". Here the tank is given and the prices are what vary, so the rule becomes "buy only as far as the next cheaper price". The two together are the standard pair for this road.

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ C ≤ 1000000000` - `1 ≤ D ≤ 1000000000` - `1 ≤ price ≤ 1000000` - `pos[0] = 0` and the positions are strictly increasing - consecutive positions differ by at most `C`, and `D - pos[n-1] ≤ C`