У вас есть грузовик, движущийся по круговой дорожке с заправочными станциями, расположенными вокруг круга. Каждая станция имеет конечное количество газа. Газовый бак на грузовике бесконечно большой. Расстояние между АЗС требует прохождения определенного количества газа. Вы можете двигаться только в одном направлении.
Каков алгоритм использования? С какой автозаправочной станции вы начинаете? Можете ли вы пройти весь путь и вернуться на стартовую станцию?
Да O (n) возможно. Определенно не TSP.
Пусть x i - количество газа, доступного на станции i, за вычетом количества газа, необходимого для перехода на следующую станцию.
Требование - & Sigma; x i & ge; 0 (достаточно газа для полного круга).
Рассмотрим S i= x 1 + x 2 +... + x i
Обратите внимание, что S n & ge; 0.
Теперь выберите самый маленький (или даже самый большой), чтобы было проще писать код для) k, так что S k является наименьшим и начинается с ближайшей станции.
Теперь для k < j & le; n, мы имеем газ в резервуаре = S j - S k & ge; 0.
для 1 & le; j & le; k, у нас есть газ в резервуаре = x k + 1 +.. + x n + x 1 + x 2 +.. + x j= S n - S k + S j & ge; 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;
}
Здесь используется подход, который работает в O(n) time и O(1) пробел (в отличие от O(n) пространства для ответа Aryabhatta).
Начните с любой станции, вызовите станцию 0 и продвигайтесь до тех пор, пока не закончите газ. Если у вас не закончится газ, сделайте это. В противном случае, если вы закончите между станциями k и k + 1, начните снова на станции k + 1. Сделайте заметку, если вы снова пройдете 0, и если вы закончите после этого, это невозможно.
Причина этого в том, что если вы начнете на станции я и закончите газ между станциями k и k + 1, то вы также закончите газ до станции k + 1, если вы начнете с любой станции между я и к.
Здесь алгоритм, заданный массивами P (бензин) и D (расстояние):
int position = 0;
int petrol = P[0];
int distance = D[0];
int start = 0;
while (start < n) {
while (petrol >= distance) {
petrol += P[++position % N] - distance;
distance = D[position % N];
if (position % N == start)
return start;
}
start = position;
petrol = P[start];
}
return -1;
Пусть cost будет массивом затрат на следующую станцию и gas будет массивом того, сколько топлива мы можем пополнить
Мы вычисляем разницу между gas[i] и cost[i], называемую diff, где я - текущая АЗС, на которой мы находимся.
Если cost[i] > gas[i] (или diff < 0), это означает, что нам нужно иметь топливо не менее cost[i] - gas[i], когда вы дойдете до станции i, чтобы перейти к следующей остановке, я + 1. Если cost[i] <= gas[i] (diff >= 0), это действительная начальная точка, потому что мы можем начать без газа, заполнить и перейти на следующую станцию. В худшем случае мы достигнем следующей остановки с пустым баком. В лучшем случае у нас будет дополнительное топливо, оставшееся до достижения я + 1 (diff > 0)
На самом деле нам не нужно начинать с одной станции, успешно пройтись по газовым заправочным станциям, чтобы узнать, есть ли действующий тур! Пока суммированное топливо >= суммарная стоимость, будет действительный тур. Поэтому нам просто нужно выполнить O (n) -проход массивов
Другие анализы:
Case1: Танк падает ниже 0
Это произойдет только при остановке, где diff < 0. После этого может быть еще одна отправная точка, которая накапливает достаточное количество избыточного топлива после прохождения одного раунда, чтобы пройти эту станцию. Тем не менее, все те станции, которые мы прошли раньше, не помогут, поэтому нам не нужно их рассматривать (см. Объяснение случая 2).
Случай 2: Текущий бак >= 0, но мы сталкиваемся с другой допустимой начальной точкой
Мы можем смело игнорировать это, потому что:
A - B - C. Если B может достигнуть C, а A может достигнуть B, то A может достигнуть C.
Случай 3: Текущий резервуаp >= 0, а не действительная начальная точка
Продолжайте переход к следующему
Случай 4: удалось достичь исходной отправной точки!
Yay!
def find_starting_station(gas, cost):
sum_gas = sum_cost = tank = start = 0
for i in range(0, len(gas)):
sum_gas += gas[i]
sum_cost += cost[i]
tank += gas[i] - cost[i]
if tank < 0:
tank = 0
start = i+1
if sum_gas < sum_cost:
return -1
return start
Это основная проблема суммарной суммы субарах. С другой стороны, мы можем смотреть на него из нескольких разных POV. Давайте выясним, где у нас будет наибольшая нехватка топлива, если мы начнем путешествие с самой первой бензоколонки. Поскольку мы знаем, что достижение этой точки должно максимально использовать топливо, мы можем заключить, что грузовик должен начать с этого момента, чтобы свести к минимуму отрицательный баланс топлива. Ниже приведено решение с программой драйвера с O (N) временем и сложностью пространства O (1), и нет необходимости в каком-либо DP, поскольку все выполняется за один проход и использует только два целых числа для хранения индекса начальной точки и его значение (хотя это необходимо только для целей печати).
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <vector>
#include <algorithm>
using namespace std;
int gasoline[] = {8, 6, 30, 9, 15, 21, 2, 18};
int stations[] = {15, 8, 2, 6, 18, 9, 21, 30};
int rnd_num(const int& low, const int& high)
{
int rndnum = (int) (((double) rand() / (double) RAND_MAX) * (high - low + 1) + low);
return rndnum;
}
void swap(int data[], const int& idxlow, const int& idxhigh)
{
int tmp = data[idxlow];
data[idxlow] = data[idxhigh];
data[idxhigh] = tmp;
}
void print_array(const char* label, int data[], int size)
{
printf("%-10s: ", label);
for (int i = 0; i < size; ++i){
printf("%-3d ", data[i]);
}
printf("\n");
}
void print_vector(const char* label, const vector<int>& data)
{
printf("%-10s: ", label);
for (vector<int>::size_type i = 0; i < data.size(); ++i){
printf("%-3d ", data[i]);
}
printf("\n");
}
void shuffle(int data[], int size)
{
for (int i = 0; i < size - 1; ++i){
int idx = rnd_num(i + 1, size - 1);
swap(data, i, idx);
}
}
void run(int gas[], int dist[], int size)
{
vector<int> path;
int diff = 0, vidx, minidx = 0, minval = gas[0] - dist[0];
path.resize(size);
for (int i = 0; i < size; ++i) {
diff += gas[i] - dist[i];
if (i == size - 1){
vidx = 0; //path[0] = diff;
}
else {
vidx = i + 1; //path[i + 1] = diff;
}
path[vidx] = diff;
if (diff < minval) {
minval = diff;
minidx = vidx;
}
}
print_vector("PATHS ", path);
printf("MINIDX: %d\nMINVAL: %d\n", minidx, minval);
}
int main()
{
int size = sizeof(stations)/sizeof(stations[0]);
srand((unsigned)time(NULL));
shuffle(gasoline, sizeof(gasoline)/sizeof(gasoline[0]));
shuffle(stations, sizeof(stations)/sizeof(stations[0]));
print_array("GASOLINE ", gasoline, sizeof(gasoline)/sizeof(gasoline[0]));
print_array("STATIONS ", stations, sizeof(stations)/sizeof(stations[0]));
run(gasoline, stations, size);
return 0;
}
начиная с любой станции, попробуйте перейти к следующему (справа). Если вы не можете (закончите газ), мы должны взять газ слева от начальной точки (переместить стартовую станцию влево).
start = 0
end = start
amount = 0
for i in range(n):
if amount > 0:
amount += (gas[end] - cost[end])
end = (end + 1) % n
else:
start = (start - 1 + n) % n
amount += (gas[start] - cost[start])
if amount >= 0: return start
return -1
`
Вот мое решение в python. Дополнение к другому объясняется, когда мы сохраняем переменную для вычисления потребности в предыдущих станциях, и когда мы находимся в конце массива, мы просто проверяем, находится ли наш остаток выше этой потребности и соответственно возвращаются.
if not gas or not cost:
return - 1
index = 0
start = 0
total = 0
need = 0
while index < len(gas):
# If we can travel without any leftover.
# What is our status since start, if total is
# below zero that means we are in a worse situation
# then we were.
total += gas[index] - cost[index]
if total < 0 :
need -= total
start = index + 1
total = 0
index += 1
if total - need >= 0:
return start
else:
return -1
Решение этой проблемы основано на жадном алгоритме. Он основан на следующих двух наблюдениях.
если общий газ > стоимость, должен быть начальный индекс для завершения круга, иначе его нет;
относительно индекса i, если из i, j - первый индекс, которого мы не можем достичь, то любой индекс от я до j не может быть начальным индексом.
Для получения более подробного описания ознакомьтесь со следующей ссылкой: Проблема с бензоколонкой.