Задача про заправки (Gas Station)

Решение: Задача про заправки (Gas Station)

Ключевое наблюдение

Эта задача решается одним проходом благодаря важному свойству:

Если общее количество топлива >= общего расхода, решение всегда существует. Нужно только найти правильную стартовую точку.

Стратегия поиска стартовой точки:

• Если мы начнём со станции i и в какой-то момент баланс станет отрицательным, то начинать нельзя ни с какой станции от i до текущей точки
• Попытаемся начать со следующей станции

Полное решение

int canCompleteCircuit(std::vector<int>& gas, std::vector<int>& cost) {
    int n = gas.size();
    int totalGas = 0;
    int totalCost = 0;
    int currentFuel = 0;
    int startStation = 0;
    
    for (int i = 0; i < n; ++i) {
        totalGas += gas[i];
        totalCost += cost[i];
        currentFuel += gas[i] - cost[i];
        
        // Если баланс отрицателен, начинать нужно не отсюда
        if (currentFuel < 0) {
            startStation = i + 1;  // пробуем начать со следующей
            currentFuel = 0;       // сбрасываем баланс
        }
    }
    
    // Если общего топлива хватает — есть решение
    if (totalGas >= totalCost) {
        return startStation;
    }
    
    return -1;
}

Трассировка примера 1

gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]

totalGas = 1+2+3+4+5 = 15 totalCost = 3+4+5+1+2 = 15 15 >= 15 ✓ → Ответ: 3

Проверка: путь от станции 3

Станция 3: бак = 0 + 4 = 4, едим до 4 (расход 1) → бак = 3
Станция 4: бак = 3 + 5 = 8, едим до 0 (расход 2) → бак = 6
Станция 0: бак = 6 + 1 = 7, едим до 1 (расход 3) → бак = 4
Станция 1: бак = 4 + 2 = 6, едим до 2 (расход 4) → бак = 2
Станция 2: бак = 2 + 3 = 5, едим до 3 (расход 5) → бак = 0 ✓

Трассировка примера 2

gas = [2, 3, 4]
cost = [3, 4, 3]

totalGas = 2+3+4 = 9 totalCost = 3+4+3 = 10 9 < 10 → Ответ: -1

Почему это работает?

Лемма: Если мы начнём со станции i и не сможем достичь станции j (топливо < 0), то ни одна станция между i и j-1 не может быть стартовой точкой.

Доказательство:

• Пусть мы в точке i имеем 0 топлива
• При прямом пути от i к j баланс в точке j < 0
• Если начнём со станции k (где i < k < j), у нас будет меньше топлива
• Потому что мы потеряли топливо на пути i → k

Глобальный критерий:

• Если totalGas >= totalCost, решение существует
• Нужно только найти правильную стартовую точку
• Правильная точка — та, с которой мы не сталкиваемся с дефицитом топлива

Анализ сложности

• Временная сложность: O(n) — один проход по массиву
• Пространственная сложность: O(1) — только несколько переменных

Почему наивный подход неправильный

// ❌ НЕПРАВИЛЬНО: O(n²)
for (int start = 0; start < n; ++start) {
    int fuel = 0;
    bool valid = true;
    for (int i = 0; i < n; ++i) {
        int idx = (start + i) % n;
        fuel += gas[idx] - cost[idx];
        if (fuel < 0) {
            valid = false;
            break;
        }
    }
    if (valid) return start;
}
return -1;

Этот подход проверяет каждую стартовую точку отдельно → O(n²).

Наше решение пропускает невозможные стартовые точки на лету → O(n).

Примеры применения в жизни

1. Дозаправка в автопути — найти оптимальную стартовую АЗС
2. Логистика — маршрут грузовика с ограниченным топливом
3. Доставка посылок — оптимальный начальный пункт
4. Микрофинансирование — последовательность платежей с минимальным остатком

Полный код с комментариями

#include <vector>
#include <iostream>

int canCompleteCircuit(std::vector<int>& gas, std::vector<int>& cost) {
    int n = gas.size();
    int totalGas = 0;      // общее количество топлива на всех станциях
    int totalCost = 0;     // общий расход топлива на весь маршрут
    int currentFuel = 0;   // текущий баланс топлива (с одной стартовой точки)
    int startStation = 0;  // индекс стартовой станции
    
    for (int i = 0; i < n; ++i) {
        totalGas += gas[i];
        totalCost += cost[i];
        currentFuel += gas[i] - cost[i];
        
        // Если баланс стал отрицательным, начинать со станции startStation нельзя
        // Это означает, что между startStation и i нет жизнеспособной стартовой точки
        if (currentFuel < 0) {
            startStation = i + 1;  // пробуем начать со следующей станции
            currentFuel = 0;       // сбрасываем баланс для новой попытки
        }
    }
    
    // Если общего топлива хватает для прохождения всего маршрута
    if (totalGas >= totalCost) {
        return startStation;
    }
    
    return -1;  // иначе решения не существует
}

int main() {
    // Тест 1
    std::vector<int> gas1 = {1, 2, 3, 4, 5};
    std::vector<int> cost1 = {3, 4, 5, 1, 2};
    std::cout << "Test 1: " << canCompleteCircuit(gas1, cost1) << " (expected 3)\n";
    
    // Тест 2
    std::vector<int> gas2 = {2, 3, 4};
    std::vector<int> cost2 = {3, 4, 3};
    std::cout << "Test 2: " << canCompleteCircuit(gas2, cost2) << " (expected -1)\n";
    
    // Тест 3: одна станция
    std::vector<int> gas3 = {5};
    std::vector<int> cost3 = {4};
    std::cout << "Test 3: " << canCompleteCircuit(gas3, cost3) << " (expected 0)\n";
    
    // Тест 4: стартуем со станции 0
    std::vector<int> gas4 = {10, 1, 1, 1};
    std::vector<int> cost4 = {1, 10, 1, 1};
    std::cout << "Test 4: " << canCompleteCircuit(gas4, cost4) << " (expected 0)\n";
    
    return 0;
}

Граничные случаи

// n = 1, можем завершить
assert(canCompleteCircuit({5}, {4}) == 0);

// n = 1, не можем завершить
assert(canCompleteCircuit({3}, {4}) == -1);

// Все станции одинаковые
assert(canCompleteCircuit({1, 1, 1}, {1, 1, 1}) == 0);

// Дефицит в конце
assert(canCompleteCircuit({1, 2, 3, 3}, {2, 3, 3, 0}) == 0);