5242. Круговой маршрут по заправкам
Medium
1 решил
Есть
Автомобиль начинает с пустым баком. Выберите одну стартовую станцию и попробуйте проехать полный круг, заезжая на каждую станцию ровно по одному разу и вернувшись к старту. В любой момент бак не должен стать отрицательным (если на участке не хватает топлива — маршрут с этого старта невозможен).
Верните индекс стартовой станции, с которой полный круг возможен. Гарантируется, что таких стартов не больше одного. Если ни один старт не подходит — верните
n заправок, стоящих по кругу. На станции i вы заливаете gas[i] единиц топлива, а чтобы доехать до следующей станции (i+1) % n, нужно потратить cost[i] единиц.Автомобиль начинает с пустым баком. Выберите одну стартовую станцию и попробуйте проехать полный круг, заезжая на каждую станцию ровно по одному разу и вернувшись к старту. В любой момент бак не должен стать отрицательным (если на участке не хватает топлива — маршрут с этого старта невозможен).
Верните индекс стартовой станции, с которой полный круг возможен. Гарантируется, что таких стартов не больше одного. Если ни один старт не подходит — верните
-1.gas = [1, 2, 3, 4, 5] cost = [3, 4, 5, 1, 2] индекс: 0 1 2 3 4 Старт с 3: бак: 0 ст.3: +4 → бак 4, едем (cost 1) → бак 3 ст.4: +5 → бак 8, едем (cost 2) → бак 6 ст.0: +1 → бак 7, едем (cost 3) → бак 4 ст.1: +2 → бак 6, едем (cost 4) → бак 2 ст.2: +3 → бак 5, едем (cost 5) → бак 0 (вернулись к 3) Бак нигде не ушёл в минус → ответ 3
Примеры:
Вход:
{"gas": [1, 2, 3, 4, 5], "cost": [3, 4, 5, 1, 2]}
Выход:
3
Объяснение: Со станции 3: заливаем 4, до следующей тратим 1 — остаётся запас, и его хватает на весь круг (см. разбор в условии). Со станций 0–2 круг оборвётся раньше. Ответ 3.
Вход:
{"gas": [2, 3, 4], "cost": [3, 4, 3]}
Выход:
-1
Объяснение: Всего топлива 2+3+4=9, а на круг нужно 3+4+3=10. Независимо от старта полного круга не получится → -1.
Вход:
{"gas": [1, 2], "cost": [2, 1]}
Выход:
1
Объяснение: Старт с 0: +1, едем за 2 — бака не хватает. Старт с 1: +2, едем за 1 → остаётся 1; на станции 0: +1 → 2, едем за 2 → 0, круг закрыт. Ответ 1.
Вход:
{"gas": [5], "cost": [4]}
Выход:
0
Объяснение: Одна станция: заливаем 5, «круг» — один переезд к себе же за 4. 5 ≥ 4 → старт 0.
Ограничения:
1 <= gas.length == cost.length <= 10^5
0 <= gas[i], cost[i] <= 10^4
подходящий старт существует не более чем в одном экземпляре
Решите эту задачу в браузере
Создайте бесплатный аккаунт — редактор Python, Java, JavaScript и Go, проверка на тестах за секунды.
Комментарии (0)
Зарегистрируйтесь или войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!