C/C++

Leetcode возвращается. Gas Station. Выбрать заправочную станцию, от которой грузовик может проделать полный круг.

Есть грузовик с неограниченным топливным баком и n заправочных станций. Для каждой станции заданы количество имеющегося на ней топлива gas[i] и расход топлива cost[i] до следующей станции. Нужно вернуть индекс от нуля до n-1 включительно той станции, начиная с которой грузовик сможет проделать полный круг (после n-1 идёт 0-я станция). Изначально бак грузовика пуст. Если такой станции нет, то вернуть -1.

Ограничения кода:
 n == gas.length == cost.length

1
Иван Брыксин
Иван Брыксин
87 571
Нам нужны только дельты (разность кол-ва топлива на заправке и расхода топлива до следующей заправки) и номера заправок.
  1. Объединяем все непрерывные последовательности заправок с одним знаком дельты (считаем, что 0 - положительное число) в одну заправку с суммарной дельтой и номером, равным номеру первой заправки в последовательности.
    В результате получаем кольцевой список с чередованием положительных и отрицательных дельт.
  2. Если длина списка равна 1 и дельта положительна - выводим номер заправки; если длина списка равна 1 и дельта отрицательна - выводим -1.
  3. Каждую пару соседних заправок "положительная дельта, за которой следует отрицательная дельта" объединяем в одну заправку с суммарной дельтой и номером заправки с положительной дельтой.
    В результате выполнения пункта 3 длина списка сокращается в 2 раза.
  4. Переходим к пункту 1.

Таким образом, на каждой итерации (реализуемой за O(текущая_длина_списка)) кол-во заправок гарантировано уменьшается в 2 раза и суммарно получаем O(n).
ЕЧ
Евгений Черняев
85 167
Лучший ответ
Иван Брыксин п1. Допустим, объединили для i = 0, схлопнули первую тысячу остановок, потом для i = 1000 схлопнули вторую тысячу остановок с другим знаком. Как это поможет рассчитывать для i = 1, i = 100, i = 1003?
Иван Брыксин А, кажись, понял. Нам не надо выбирать i, не равные началу последовательности положительных балансов.
Иван Брыксин 99.6% участников были уделаны по скорости.
С замерами памяти там беда, редко показывает высокий результат. Я сделал в каждой итерации новый вектор и подмену старого через автопоинтер. Попробую ещё через ковыряния в одном и том же массиве, может, так меньший расход покажет.
Иван Брыксин И ещё нюанс - нулевые дельты нужно относить к отрицательным, считается, что машина с пустым баком путешествовать не может, даже если стоимость путешествия = 0. В условии не написано, пришлось догадываться из тестовых данных. 
 class Solution { 

public: 

    int canCompleteCircuit(vector& gas, vector& cost) 

    { 

        int pos = 0, forward_len = 0, ended_len = 0; 

        int forward_balance = 0,ended_balance = 0; 

        int start_pos; 

        while ( forward_len+ended_len < gas.size()) 

        { 

            forward_len++; 

            forward_balance += gas[pos]-cost[pos]; 

            if (forward_len == 1) start_pos = pos; 

            if (forward_balance < 0) 

            { 

                ended_balance += forward_balance; 

                ended_len += forward_len; 

                forward_balance = 0; 

                forward_len = 0; 

            } 

            pos++; 

        } 

        return forward_balance+ended_balance>=0?start_pos:-1; 

         

    } 

};
Gurban Jumageldiyew
Gurban Jumageldiyew
51 417
пусть мы проедем 2^i отрезков пути, начиная с j-й станции
пусть r[i][j] - сколько топлива у нас останется в конце, m[i][j] - минимальное количество топлива, которое у нас будет за всю поездку
r[0][j] = m[0][j] = gas[j]-cost[j]
r[i+1][j] = r[i][j] + r[i][(j+2^i) mod n], m[i+1][j] = min(m[i][j], r[i][j] + m[i][(j+2^i) mod n])
ответ - j такое, что m[ceil(log(n))+1][j]>=0
сложность O(n log n)

похоже на правду?
Сергей Афанасьев
Сергей Афанасьев
36 952
Иван Брыксин Для того, чтобы рассчитать r[i][j] и m[i][j], нужен сам по себе квадратичный алгоритм, структуры-то квадратичные. И к вычислительной сложности ещё добавится 2 массива по 100 млрд элементов, и вся эта кухня займёт 800 гигабайт. Не думаю, что стоит это пробовать.
Понимаю, что вы ищете более эффективное решение задачи. Ваш текущий код осуществляет полный перебор стартовых точек, что может быть неоптимальным для больших входных данных.

Для того чтобы решить эту задачу с более оптимальным временем исполнения, можно использовать греедный алгоритм. Вам необходимо найти индекс станции, с которой грузовик сможет проделать полный круг, используя только один проход по данным. Вот общий алгоритм:

1. Вычислите разницу между количеством топлива и расходом топлива для каждой станции (gas[i] - cost[i]).
2. Ищите индекс, с которого начав, вы всегда имеете положительную сумму разницы (баланс) на каждом шаге. То есть, начните с индекса 0 и двигайтесь вперед, накапливая баланс. Если в какой-то момент баланс становится отрицательным, это означает, что начиная с текущей станции, грузовик не сможет проделать полный круг. Тогда выбираем следующую станцию в качестве потенциальной стартовой и продолжаем анализ.
3. Если после обхода всех станций у вас есть положительный баланс, то это означает, что грузовик может совершить полный круг, начиная с индекса, который вы выбрали на шаге 2.

Вам необходимо реализовать этот греедный алгоритм, чтобы решить задачу более эффективно для больших входных данных.
Илья Агафонов
Илья Агафонов
14 368
Иван Брыксин То, что ты советуешь, имеет ровно такую же неэффективную асимптотику.

Похожие вопросы