Все задачи
Легко Решена: 1 Процент решений: 9.1%

Сделайте массив неубывающим

Найдите минимальное количество увеличений, чтобы каждое значение было не меньше предыдущего.

Чему вы научитесь

  • Исправлять каждое значение относительно предыдущего
  • Считать общее число нужных ходов
  • Понять, почему жадный выбор оптимален

Условие

За один ход можно увеличить один элемент массива на 1. Сделайте массив неубывающим: каждое значение должно быть больше либо равно предыдущему. Уменьшать значения или менять их порядок нельзя.

Реализуйте функцию increasing_array(numbers).

Входные данные

numbers: значения в исходном порядке.

Выходные данные

Верните минимальное общее количество единичных увеличений.

Ограничения

1 ≤ длина ≤ 200 000. Каждое значение от 1 до 1 000 000 000. Используйте знаковый 64-битный результат.

Примеры

Пример 1
Ввод:
numbers = [4, 1, 3]

Ожидаемый вывод:
expected = 4
Ввод:
std::vector<long long> numbers = {4, 1, 3};

Ожидаемый вывод:
long long expected = 4;
Ввод:
long[] numbers = new long[] {4, 1, 3};

Ожидаемый вывод:
long expected = 4;

Пояснение

Повысим 1 до 4 за три хода и 3 до 4 за один ход. Получится [4, 4, 4] с четырьмя ходами.

Пример 2
Ввод:
numbers = [1, 2, 2, 5]

Ожидаемый вывод:
expected = 0
Ввод:
std::vector<long long> numbers = {1, 2, 2, 5};

Ожидаемый вывод:
long long expected = 0;
Ввод:
long[] numbers = new long[] {1, 2, 2, 5};

Ожидаемый вывод:
long expected = 0;

Пояснение

Каждое значение уже не меньше предыдущего; одинаковые соседние значения допустимы.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Идите слева направо, потому что каждое значение зависит только от предыдущего.

Подсказка 2

Если значение слишком мало, увеличьте его ровно настолько, чтобы оно достигло текущего минимально допустимого значения.

Подсказка 3

Тщательно считайте общее число увеличений, так как ранние изменения влияют на следующие сравнения.

Ожидаемая сложность

O(n) по времени, O(1) доп. памяти

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

# Участник Язык Время Память Оценка ИИ Решение
1 HJhettory Jurash Python 803 ms - 4/5 Посмотреть код

Учитесь у других

Решения сообщества

Внимание, спойлер: ниже 1 полное решение Попробуйте сначала решить сами. Вы всегда можете посмотреть код других и AI-обзоры. Войдите и решите задание, чтобы присоединиться к обсуждению.