Алгоритм для грузовика, перемещающего круг автозаправочных станций

Question

Алгоритм для грузовика, перемещающего круг автозаправочных станций

У Вас есть грузовик, перемещающий круговую дорожку с автозаправочными станциями, растянутыми вокруг круга. Каждая станция имеет конечное количество газа. Бензобак на грузовике является бесконечно большим. Расстояние между автозаправочными станциями требует, чтобы определенное количество газа пересекло. Можно только переместиться в одно направление.

Что должен использовать алгоритм? В какой автозаправочной станции Вы запускаете? Можно ли добраться полностью вокруг и назад к станции запуска?

19

algorithm

задан paxos1977 8 May 2014 в 22:14

1 ответ

Другие вопросы по тегам:

algorithm

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

score 25 · Accepted Answer

Да, O(n) возможно. Определенно не TSP.

Пусть x_i - это количество бензина, доступное на станции i, минус количество бензина, необходимое для поездки на следующую станцию.

Требованием является Σ x_i ≥ 0 (достаточно газа для прохождения полного круга).

Рассмотрим S_i = x₁ + x₂ + ... + x_i

Заметим, что S_n ≥ 0.

Теперь выберем наименьшее (или даже наибольшее, для которого проще написать код) k такое, что S_k будет наименьшим, и начнем со станции рядом с ним.

Теперь для k < j ≤ n, имеем газ в баке = S_j - S_k ≥ 0.

для 1 ≤ j ≤ k, имеем газ в баке = x_k+1 + ... + x_n + x₁ + x₂ + .... . + x_j = S_n - S_k + S_j ≥ 0.

Таким образом, старт с k+1 обеспечит достаточное количество бензина, накопленного на каждой станции, чтобы добраться до следующей станции.

// C++ code. gas[i] is the gas at station i, cost[i] is the cost from station i to (i+1)%n
int circ(vector<int> &gas, vector<int> &cost) {
    int min_S=INT_MAX, S=0, position=0;
    for(int i=0;i<gas.size();i++)
    {
        S += gas[i] - cost[i];
        if(S<min_S)
        {
            min_S = S;
            position = (i+1) % gas.size();
        }
    }
    if(S>=0)
        return position;
    else
        return -1;
}