Найти минимальное количество операций для очистки массива

Question

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

1. Удалить любую рыбу из пруда
2. Добавить рыбу любого размера в пруд

Учитывая начальный размер крокодила и массив рыб в пруду, мы должны найти минимум нет. таких операций, чтобы очистить массив, представляющий пруд.

Например,

Начальный размер крокодила - 20, а массив рыб -

[10,15,20,30,100]

В этом случае крокодил съедает всех рыб, кроме 100, и его размер становится 85, поэтому одним из решений может быть удаление рыбы с размером 100. Таким образом, результат будет 1.

Каков наилучший из возможных алгоритмов для реализации вышеуказанной проблемы, может ли он быть решен рекурсивно?

Answer 1

Итак, прежде всего, отсортируйте массив.Крокодил съест каждую рыбу, которая меньше его.Начните слева, если крокодил может съесть рыбу, увеличьте его размер.Если рыбы не осталось, верните 0. Если нет, сделайте две переменные, потенциальный результат = бесконечность и действия = 0. Один из возможных ответов - удаление остальной рыбы.Установить результат как минимум (результат, fish_left + actions).Затем попробуйте добавить новую рыбу.Вы всегда хотите, чтобы крокодил рос как можно больше, поэтому вставьте рыбу, размер которой на 1 меньше, чем у крокодила (умножьте ее размер на 2 и уменьшите на 1).Увеличьте действия на один.Пусть крокодил съест всю возможную рыбу.Повторяйте, пока вся рыба не будет съедена, затем верните результат.Если цифры действительно велики, вы можете добавить тонны рыбы, так как же нам ее преодолеть?Ну, ваш минимальный ответ до сих пор является результатом.Если вы когда-либо совершите больше действий, чем ваш текущий результат, вы не сможете получить лучший, поэтому вы можете завершить цикл и вернуть результат.Итак, наша сложность O (n) - размер массива.Не могу представить более быстрый.РЕДАКТИРОВАТЬ: На самом деле O (N журнала N) из-за сортировки.И вы можете делать все рекурсивно (буквально все), но я не вижу смысла делать это здесь.