Comentário por Henrique Vianna
Conhecimento prévio necessário:
Perceba, primeiramente, que sempre faz sentido enfrentar o monstro mais fraco entre aqueles que ainda não foram derrotados. Para isso, deve-se usar a fada mais fraca possível (que ainda não tenha usado seu “bônus” completamente), que consiga derrotá-lo. Então, basta simular esse processo para maximizar o número monstrinhos que Fefe consegue derrotar. Para tanto, pode-se ordenar tanto as fadas quanto os monstros em ordem crescente de poder, e depois selecionar, para cada fada, quais monstros ela enfretará. Para a fada sendo processada no momento, deve-se selecionar repetidamente o monstro de menor poder até que uma das seguinte condições seja verdade: a fada enfrentou o máximo de monstros que pode, a fada não consegue derrotar mais nenhum monstro, todos os monstros foram derrotados. No código abaixo, esse algoritmo é simulado usando a técnica de two pointers (pelos limites é possível também fazer isso mais lentamente, em 
).
Segue o código:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int MAX = 1550; | |
| int n, f, e[MAX]; | |
| int32_t main(void) | |
| { | |
| ios_base::sync_with_stdio(false); | |
| cin.tie(NULL); | |
| cin >> n >> f; | |
| for(int i = 1; i <= n; i++) cin >> e[i]; | |
| vector<pair<int, int>> pb(f); | |
| for(auto &[p, b] : pb) cin >> p; | |
| for(auto &[p, b] : pb) cin >> b; | |
| sort(e + 1, e + 1 + n); | |
| sort(pb.begin(), pb.end()); | |
| int numMonstro = 0; | |
| for(auto [p, b] : pb) | |
| while(b > 0 && p > e[numMonstro + 1] && numMonstro + 1 <= n) numMonstro++, b–; | |
| cout << numMonstro << '\n'; | |
| } |