Rental Car-Editorial
We consider starting from every petrol pump one by one using a while loop. We take two variables to check if the car will be able to make it or not.
d which gives the difference between the oil offered by a pump and the distance between the next station.
Sum is checked to see whether starting at a specific pump will be a solution or not. When sum goes below zero we check for the next pump.
C++ code:
#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
lli oil[100000 + 10];
lli dis[100000 + 10];
int n;
int main(void) {
int i, j, k, kase = 0;
cin >> n;
for (i = 0; i < n; i++)
cin >> oil[i] >> dis[i];
int st, en;
en = 0, st = 0;
lli sum = 0, d;
while (st + 1 != en) {
d = oil[st] - dis[st];
if (sum + d >= 0)
st++, sum += d;
else
sum = 0, st++, en = st;
if (st >= n)
st -= n;
}
printf("%d\n", en);
return 0;
}