Ctrl K

Вычёркивание с самого маленького

Средняя
Дан массив положительных чисел values. Изначально ни одно число не вычеркнуто, а счёт равен нулю. Повторяйте, пока в массиве остаются невычеркнутые числа: 1. Возьмите наименьшее невычеркнутое число. Если таких несколько, возьмите то, что стоит левее всех. 2. Прибавьте его к счёту. 3. Вычеркните его и соседей слева и справа (если они есть; уже вычеркнутые соседи так и остаются вычеркнутыми). Верните итоговый счёт.
Пример 1
values=[4, 2, 7, 1, 3] → 3

Сначала берём 1 (индекс 3) и вычёркиваем её вместе с 7 и 3. Из оставшихся 4 и 2 меньше 2 — берём её, вычёркивается и 4. Счёт 1 + 2 = 3.

Пример 2
values=[5, 5, 5, 5] → 10

Все равны, поэтому берём самый левый: индекс 0 (вычёркиваются 0 и 1), затем индекс 2 (вычёркиваются 2 и 3). Счёт 10.

Пример 3
values=[9] → 9
Ограничения
  • 1 ≤ len(values) ≤ 10⁵
  • 1 ≤ values[i] ≤ 10⁶
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиОстаток на полке после заказов СредняяРазобрать стопки поровну ЛёгкаяСамая загруженная переговорка СложнаяСамые частые значения СредняяЗадания с перерывом на остывание Средняя
загружаем Python…
Вход
values=[4, 2, 7, 1, 3]
Ожидается
3

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 114 тестов на сервере, включая скрытые.