Охота на монстра

Для начала заметим, что время жизни всей команды ограничено её героем с самым низким уровнем здоровья — он погибнет первым. Допустим, что у героя с самым низким уровнем здоровья $$$m$$$ единиц здоровья. Тогда команда героев успеет атаковать монстра не больше, чем $$$m$$$ раз перед тем, как один или более героев погибнет. Пусть $$$s$$$ — это сумма величин атаки всех героев в команде, тогда перед смертью одного или более героев команда успеет нанести $$$m \cdot s$$$ единиц урона монстру. В таком случае, если $$$a \leq m \cdot s$$$, где $$$a$$$ — здоровье монстра, то команда сможет убить монстра без потерь.

Предположим теперь, что мы можем брать в команду только тех героев, здоровье которых не меньше некоторого значения $$$m$$$. Тогда очевидно, что среди всех героев со здоровьем, не меньшим $$$m$$$, выгодно брать героев с самыми большими величинами атаки. Достаточно брать очередного героя в порядке убывания силы атаки до тех пор, пока остался еще хотя бы один не взятый герой и $$$a > m \cdot s$$$.

Осталось понять, что происходит, когда требование на минимальное здоровье героя для вступления в команду возрастает, например с $$$m$$$ до $$$m+1$$$. В таком случае, если в команду входили герои со здоровьем $$$m$$$, то теперь их нужно убрать из команды. После этого суммарной атаки героев может не хватить, чтобы убить монстра за $$$m+1$$$ ход. В таком случае нужно просто добрать в команду самых сильных ещё не взятых героев.

Реализовать это можно следующим образом. Сперва отсортируем героев по возрастанию здоровья. Вначале возьмем в команду всех героев или только самых сильных героев, которых хватит для убийства монстра. Затем будем итерироваться по возрастанию минимального здоровья, необходимого для вступления в команду. Далее нам понадобится структура данных, из которой можно быстро извлекать минимальный/максимальный элемент, например, множество (std::set) в языке C++. В одном множестве будем хранить не состоящих в команде героев по убыванию силы. Во втором множестве будем хранить героев из нашей команды по возрастанию здоровья. Пусть сейчас требование на минимальное здоровье составляет $$$m_i$$$ и минимальная по количеству команда героев собрана. Обновим ответ и перейдем к следующему по возрастанию здоровью для вступления в команду $$$m_{i+1}$$$, где $$$m_{i+1} > m_i$$$. Тогда до тех пор, пока минимальный элемент в нашем множестве, хранящем героев из команды, имеет здоровье $$$m_i$$$ — будем выполнять удаление этого элемента. После этого добавляем в нашу команду из второго множества самых сильных героев, чтобы общая численность команды была такая, как до удаления. Теперь если хватает суммарной силы, то пытаемся обновить ответ. В последнюю очередь пытаемся удалить героев из команды, если их больше, чем надо. Заметим, что если в какой-то момент нам хватило $$$x$$$ героев для победы над монстром, то в будущем нам уже не будет смысла пытаться добавить в команду больше $$$x$$$ героев, так как такие ответы заведомо хуже. Мы добавляем героев в команду только взамен удаленных, а также пытаемся удалить лишних.