n заправок, пронумерованных от 0 по ходу движения. На заправке i можно залить fuel[i] единиц топлива, а дорога от неё до следующей заправки (после последней — до нулевой) сжигает burn[i] единиц. Бак бездонный, в начале пуст.
Верните номер заправки, с которой можно стартовать и проехать полный круг, ни разу не оставшись с отрицательным запасом топлива. Если такой заправки нет, верните -1.
Гарантируется, что подходящая заправка, если существует, единственная.
Перебор всех стартов работает за O(n²) — попробуйте за один проход.fuel=[2, 6, 1, 5], burn=[3, 2, 6, 2] → 3
Старт на заправке 3: бак 5 − 2 = 3, затем 3 + 2 − 3 = 2, затем 2 + 6 − 2 = 6, затем 6 + 1 − 6 = 1 — круг пройден. С любой другой заправки бак где-то уходит в минус.
fuel=[3, 1, 2], burn=[2, 3, 2] → -1
Всего топлива 6, а на круг нужно 7 — откуда ни стартуй, не хватит.
fuel=[5], burn=[5] → 0
Единственная заправка: заливаем 5 и ровно столько тратим на дорогу обратно к ней.
fuel=[2, 6, 1, 5], burn=[3, 2, 6, 2]
3
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 47 тестов на сервере, включая скрытые.