Войти Регистрация
Алгоритмы

31. Заправки на кольце

Средняя

На кольцевой трассе n заправок. gas[i] — сколько топлива дают на i-й, cost[i] — расход до следующей. Бак на старте пустой, объём не ограничен.

Верните индекс заправки, с которой можно проехать полный круг, или −1. Если подходящих несколько, верните наименьший индекс.

В работе: Откуда начать маршрут курьера по кольцу пунктов выдачи, чтобы не остаться без заряда.

Пример 1

Ввод
gas = [1, 5, 2]
cost = [3, 1, 3]
Вывод
1

С заправки 1: 5 − 1 + 2 − 3 + 1 − 3 = 1 ≥ 0 на каждом шаге.

Пример 2

Ввод
gas = [1, 1]
cost = [2, 2]
Вывод
-1

Ограничения

  • 1 ≤ n ≤ 10⁶
  • 0 ≤ gas[i], cost[i] ≤ 10⁴
  • Лимит — 1 с на тест.
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def start_station(gas, cost):
Жадный алгоритмПрефиксные суммыцельO(n)

Источник: Яндекс Практикум о секции, 2024. Условие пересказано своими словами.

Давали на собеседовании? Ответов пока мало — ваш поможет.