algo-aha

最少加油站

• https://leetcode.com/problems/minimum-number-of-refueling-stops/

int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
    // 车油足够时不加油，只把加油站油量记入最大堆；车油不够时，从堆中取最大值加油。
    const int N = stations.size();
    int maxDist = startFuel; // 能行驶的最大距离
    priority_queue<int> pq;
    int ans = 0, idx = 0;
    while (true) {
        while (idx < N && stations[idx][0] <= maxDist) {
            pq.push(stations[idx][1]);
            idx++;
        }
        if (maxDist >= target) return ans;
        if (pq.empty()) return -1; // 无油可加

        int fuel = pq.top();  pq.pop();
        maxDist += fuel;
        ans++;
    }
}

加油能否跑完一圈

• https://leetcode.com/problems/gas-station/

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    // 只要 sum(gas[i]-cost[i]) >=0 就能绕圈
    // 因为若无法绕圈，存在某站的消耗 cost[i]-gas[i] > 其他站的总积累 sum(gas[j]-cost[j])，
    // 所有站的总积累 sum(gas[i]-cost[i]) < 0 ==取逆否命题=> sum(gas[i]-cost[i]) >=0 就能绕圈

    const int N = gas.size();
    int gasSum = 0;
    int start = 0, gasFromStart = 0;
    for (int i = 0; i < N; i++) {
        int gasI = gas[i] - cost[i];
        gasSum += gasI, gasFromStart += gasI;
        if (gasFromStart < 0) { // i站及前面站不能作为起点，下一站作起点候选
            start = i + 1;
            gasFromStart = 0;
        }
    }
    if (gasSum < 0) return -1;
    return start;
}