Нужно точнее понимать правила уровня (что такое «кормить»: один кусок еды на одно чудовище, сумма кусочков, требования к порядку и т.п.). Если не можешь — пришли короткое описание (массив аппетитов и массив размеров еды или скрин).
Ниже — решения для двух типичных вариантов.
1) Один кусок еды отвечает за одно чудовище (кусок пригоден, если его размер ≥ аппетит). Цель — накормить всех или максимальное число.
- Идея: жадно сопоставлять «самому ненасытному подходящий кусок» неэффективно; правильно — сортировать оба списка и матчить маленькие с маленькими.
- Пусть аппетиты $A=[a_1,\dots ,a_n]$, размеры еды $S=[s_1,\dots ,s_m]$. Отсортируйте по неубыванию.
- Алгоритм (двух указателей):
1. Отсортировать $A$ и $S$.
2. Завести указатели $i=1$ для $A$ и $j=1$ для $S$.
3. Пока $i\le n$ и $j\le m$: если $s_j\ge a_i$ — кормим $a_i$, увеличить $i$ и $j$; иначе $j++$ (ищем больший кусок).
4. Ответ: накормлено $i-1$ чудовищ; все накормлены, если $i=n+1$.
- Сложность: сортировка $O(n\log n+m\log m)$, проход $O(n+m)$.
Пример: $A=[2,4,3]$, $S=[1,3,5]$ → после сортировки $A=[2,3,4]$, $S=[1,3,5]$: пропускаем $1$, $3\ge 2$ кормим, $5\ge 3$ кормим, осталось одно аппетит $4$ без еды.
2) Кусочки суммируются (чтобы накормить чудовище надо дать несколько кусочков, суммарный размер ≥ аппетит). Цель — накормить всех или макс. число.
- Это задача о разложении/распределении — в общем NP-трудная при больших размерах. При небольших ограничениях можно использовать динамическое программирование (битсет/knapsack) по суммам.
- Подход (для маленьких сумм): отсортировать чудовищ по аппетиту по убыванию; для каждого чудовища пытаться собрать из оставшихся кусочков подмножество суммой ≥ его аппетита (subset-sum), если получилось — удалить эти кусочки и перейти к следующему; реализуется через битсеты или DP.
- Если суммарная длина еды $T=\sum S$ и $T$ невелико (например $T\le 10^5$), можно поддерживать битсет возможных сумм и для выбора конкретных кусочков восстанавливать набор.
- Если количества большие — думать о жадных эвристиках (давать большие куски большим аппетитам) или о ILP/брютах с отсечением.
Если опишешь точные правила уровня (формат входных данных: массивы, ограничения на размеры и т. д.), дам конкретный пошаговый алгоритм и код/псевдокод.