Fefe e o jogos dos monstrinhos

Solução escrita por Malu Azevedo

O problema nos pede para determinar o número máximo de monstrinhos que a Fefe consegue derrotar, utilizando um conjunto de $F$ fadas (cada uma com um poder específico e um bônus que define o limite de monstrinhos que ela pode enfrentar) contra $N$ monstrinhos com diferentes poderes, sabendo que uma fada vence um monstrinho se o seu poder for maior ou igual ao do monstrinho.

Ideia Central

Para maximizar a quantidade de monstrinhos derrotados, podemos utilizar uma estratégia gulosa (greedy) combinada com ordenação. Como cada fada pode enfrentar até $B_j$ monstrinhos desde que o seu poder seja suficiente ($P_j \ge E_i$), precisamos associar os monstrinhos às fadas de maneira ótima. Uma abordagem eficiente consiste em ordenar os poderes dos monstrinhos e das fadas. Em seguida, para cada monstrinho, percorremos as fadas disponíveis para encontrar aquela que possui o menor poder suficiente para derrotá-lo e que ainda disponha de capacidade de bônus restante ($B_j > 0$). Essa escolha gulosa garante que não desperdiçamos fadas mais fortes em monstrinhos fáceis, preservando-as para os desafios maiores.

Abordagem Completa

Lemos a quantidade de monstrinhos $N$ e de fadas $F$, seguida pelos poderes dos monstrinhos, e pelos poderes e bônus das fadas. Armazenamos e ordenamos os dados para facilitar a busca. Em seguida, para cada monstrinho, utilizamos uma busca linear entre as fadas para alocar a fada mais adequada que atenda aos requisitos de poder e bônus, decrementando o bônus da fada escolhida e incrementando o contador de monstrinhos derrotados. Com $N \le 1500$, essa abordagem possui complexidade $O(N \cdot F)$.

Clique aqui para ver o código completo.