Алгоритмы и структуры данных: продвинутый уровень Заправки
Выпуск 5. Заправки
Здравствуйте, !
Задача. Дано два массива A и B одинакового размера N, где N - это число заправок расположенных на пути. Дорога проходит через все заправки и закольцовывается (то есть по дороге мы можем объезать все заправки и вернуться в точку старта).
Массив A показывает, сколько топлива хранится на каждой заправке i.
У вас есть машина с беконечным баком. А в массиве B элемент i
показывает, сколько топлива расходует ваша машина при переезде из точки i
в i+1.
Нужно вернуть индекс i заправки, начиная с которой вы можете объехать
все заправки, не оставшись без бензина по пути. Либо вернуть -1, если такого индекса не существует (с
какой заправки не стратуй, всё равно останешься где-то без топлива).
Пример.
Дано:
A = [1, 2]
B = [2, 1]
Ответ: 1 (индекс в массивеб то есть мы стартуем со второй заправки)
Объяснение:
Если вы стартуете с индекса 0, вы можете залить в бак A[0] = 1
единиц топлива. Но вам нужно B[0] = 2 единицы топлива, чтобы доехать
до заправки с индексом 1.
Если вы стартуете с заправки под индексом 1, вы можете залить в бак
A[1] = 2 единицы топлива. И вам нужно B[1] = 1 топлива, чтобы доехать до
заправки с индексом 0. И вы до неё доезжаете, и у вас ещё остаётся 1 единица
топлива. Вы доливаете A[0] = 1 ещё одну единицу топлива, и у вас в баке
становится 2 единицы топлива. В данной точке вам нужно B[0] = 2 единиц топлива,
чтобы доехать до заправки с номером 1 и завершить круг.
Идея решения: прежде всего, можно просуммировать все значения
требуемого топлива (из массива B) и вычесть из суммы все значения
наличного топлива (массив А), чтобы понять, решаема ли задача в
принципе. Но так мы не найдём нужный индекс, если задача решаема.
Поэтому идём по всем индексам от 0 до N и попарно вычитаем требуемое топливо из наличного (бензобак + заправка). Компилируемое Java-решение
public class Solution {
public int canCompleteCircuit(final List<Integer> gas, final List<Integer> cost) {
// проверка на ноль
if(gas == null || cost == null || gas.size() == 0 || cost.size() == 0 ||
gas.size() != cost.size())
return -1;
int n = gas.size();
int sumRemaining= 0;
int total = 0;
int start = 0;
for(int i = 0; i < n; i++){
// попарно вычитаем
int remaining = gas.get(i) - cost.get(i);
// если бак не ушёл в минус на предыдущем шаге
if(sumRemaining >= 0)
// то добавляем топливо заправки и вычитаем стоимость переезда в следующую точку
sumRemaining += remaining;
else{
// если бензобак ушёл в минус на предыдущем шаге, то мы начали не с той точки
// поэтому начинаем с текущей точки i, и заливаем remaining
sumRemaining = remaining;
start = i;
}
// а вот тут подсчитываем, решаема ли задача в принципе.
// То, что было написано в идее решения сразу же
total += remaining;
}
// если задача в принципе решаема, то сумма элементов A минус сумма элементов B
// должна быть больше нуля, а необходимый индекс start - тот,
// который ни разу не "дискредитировал" себя
if(total >= 0)
return start;
else return -1;
}
}
С уважением, Наталия Македа natalia.macheda at gmail.com 2021-03-17, Trento
Внимание! Письмо, которое вы мне отправите с вопросами и коментариями по тематике данной рассылки, может быть опубликовано полностью или частично в данной рассылке, если в нём нет явного запрета на это.
