Analysis: Fuel Economy by Fatih Gelgi


In this problem, we need to determine "in which stations to stop" and "how many units of fuel to buy". In fact, it can be considered as "how many units of fuel to buy in each station" since FJ can stop at a station and buy 0 unit. To make the decision, we need a few observations.

Consider the sample input in the problem:

0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17	=> distance
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
     40        7          15 12	                   	=> fuel price
3     1        0           6  5		           0	=> remaining fuel
      2       10           0  2                    0   	=> how much to buy
     80      150         174 174                 174	=> total cost

At the first station, FJ only buys 2 units of fuel -- the sufficient amount to go to the next cheaper station. Then he fills the tank at station 2 since there is no cheaper station afterwards. He didn't buy any fuel at station 3 since station 4 is cheaper and FJ has enough fuel to reach there.

Straightforward implementation based on the idea above requires sorting of stations with respect to the distance -- that is O(N log N). Then we need to find the next cheaper station of each station. That requires O(N) time for each station in the worst case. O(N^2) time complexity is too slow for the problem. Fortunately, we can optimize "finding the cheaper station" part using stacks. Starting from the last station, stations are pushed into the stack. At a station x, we pop the stack until the price of the station on the top is less then the price of x. The next cheaper station from x will be that one. Notice that the LIFO property of stack gives the opportunity to find the first station that is cheaper than x. We can visualize the method on the sample input as follows:

Station	Next cheaper station	Stack
-------	--------------------	-----
   4		-		  4
   3		4		  4 3
   2		-                 2
   1            2                 2 1

The running time for the stack is O(N) as illustrated. That makes the total time O(N log N) for the problem. Below is Travis's code:

#define NMAX 50000

struct station {
	int pos, cost;
	bool operator<(station const& o) const {
		return pos < o.pos;
	}
};
station stations[NMAX];

int s[NMAX];
int nextSmall[NMAX];

int main() {
#ifndef HOME
	freopen("fuel.in","r",stdin);
	freopen("fuel.out","w",stdout);
#endif

	int n, maxGas, curGas, dist;
	scanf("%d %d %d %d", &n, &maxGas, &curGas, &dist);
	for (int i = 0; i < n; i++) {
		scanf("%d", &stations[i].pos);
		scanf("%d", &stations[i].cost);
	}
	sort(stations, stations + n);

	// find next cheaper station for each station
	int stacklen = 0;
	for (int i = n-1; i >= 0; i--) {
		while (stacklen > 0 && stations[s[stacklen-1]].cost >= stations[i].cost) {
			stacklen--;
		}
		nextSmall[i] = (stacklen == 0 ? -1 : s[stacklen-1]);
		s[stacklen] = i;
		stacklen++;
	}

	curGas -= stations[0].pos;	// move to station 1
	long long cost = 0;
	for (int i = 0; i < n; i++) {
		// gas is less than 0 means it is impossible to reach the station
		if (curGas < 0) {
			printf("-1\n");
			return 0;
		}
		int gasNeeded = min(maxGas, (nextSmall[i] == -1 ? dist :
stations[nextSmall[i]].pos) - stations[i].pos);
		if (gasNeeded > curGas) {
			cost += (long long) (gasNeeded - curGas) * (long long) stations[i].cost;
			curGas = gasNeeded;
		}
		curGas -= (i == n-1 ? dist : stations[i+1].pos) - stations[i].pos;
	}

	if (curGas < 0) {
		printf("-1\n");
	} else {
		printf("%lld\n", cost);
	}
}