Крупная закупка

Сформулируем задачу кратко: дано $$$n$$$ видов оружия, требуется купить $$$m$$$ штук, из которых найдется хотя бы $$$k$$$ разных видов. При этом требуется максимизировать суммарную мощность оружия, а при равной мощности минимизировать максимальное количество оружия одного вида.

Первым шагом отсортируем виды оружия по убыванию мощности. Пусть теперь $$$a_1 \geqslant a_2 \geqslant \ldots \geqslant a_n$$$. Заметим, что имеют место следующие факты:

  1. в каком-то оптимальном наборе есть хотя бы по одному экземпляру оружия каждого из первых $$$k$$$ видов (потому что всего есть хотя бы $$$k$$$ различных видов, и не уменьшая суммарную мощность можно заменить все оружие мощности $$$a_i$$$ на оружие мощности $$$a_{j<i}$$$)
  2. если $$$a_1 = a_2 = \ldots = a_i \neq a_{i+1}$$$, то больше одного экземпляра можно брать только у видов $$$1 \ldots i$$$, потому что в ином случае суммарная мощность будет не максимальна
  3. таким образом, если $$$i \leqslant k$$$, следует взять по одному экземпляру каждого из первых $$$k$$$ видов, а оставшиеся $$$m - k$$$ наиболее равномерно распределить по первым $$$i$$$ видам
  4. если же $$$i > k$$$, то выгодно наиболее равномерно распределить все $$$m$$$ штук по первым $$$i$$$ видам, так как это минимизирует максимальное количество одного и того же вида

Подгруппа (1) решалась первыми двумя наблюдениями, достаточно было понять, что надо взять по одному экземпляру каждого из $$$k$$$ наиболее мощных видов, и еще $$$m - k$$$ экземпляров самого мощного.

Подгруппа (2) требовала выбрать по одному экземпляру каждого из $$$k$$$ максимальных видов, а в подруппе (3) следовало заметить, что если первые $$$i > k$$$ видов одинаковы по мощности, в оптимальном ответе будет $$$i$$$ видов, а не $$$k$$$.

Полное решение заключается в проверке отношения между $$$k$$$ и количеством максимальных по мощности видов оружия $$$i$$$, и выводе $$$\max(i, k)$$$ первых видов и распределения оставшихся $$$m - \max(i, k)$$$ экземпляров примерно поровну (с отличием количества разных видов не более, чем на один) по $$$i$$$ абсолютно максимальным по мощности видам оружия.