lxviii. Gas Station Circuit

Problem. $n$ gas stations on a circle; station $i$ gives $g_i$ fuel and reaching the next one costs $c_i$. Find a start from which you can complete the circuit with an initially empty tank, or report none.

Answer: a start exists iff $\sum g_i\ge \sum c_i$; one pass finds it: whenever the running tank goes negative, the next station becomes the candidate start.

int gasStart(const vector<long long>& gas, const vector<long long>& cost) {     // start index completing the circuit, or -1
    long long total = 0, tank = 0; int start = 0;
    for (int i = 0; i < sz(gas); i++) {
        total += gas[i] - cost[i]; tank += gas[i] - cost[i];
        if (tank < 0) start = i + 1, tank = 0;
    }
    return total >= 0 ? start : -1;
}

Proof: the one-pass greedy

If the tank first becomes negative after station $i$ when starting at $s$, then no station in $s..i$ works as a start: starting at any $t$ in between, you arrive at $t$ with a non-negative tank from $s$, so starting at $t$ with an empty tank can only be worse, and it also fails by station $i$. So the candidate jumps to $i+1$. Let $s$ be the final candidate: the suffix from $s$ to $n-1$ never goes negative, and the prefix $\mathrm{0..}s-1$ has total $\text{total}-\text{suffix}$. If the total is $\ge 0$, the suffix surplus covers every prefix deficit (each prefix sum is at least $-\text{suffix}$, otherwise the total would be negative), so the circuit from $s$ succeeds. If the total is negative, no start works because the whole circuit consumes more than it gives. Checked against trying every start.