Solução por Leonardo Paes
A observação mais importante é que:
- Uma chave com id ímpar só pode ser usada para abrir um baú com id par.
- Uma chave com id par só pode ser usada para abrir um baú com id ímpar.
Seja:
- $$b_{0}, b_{1}$$ o número de baús com id par e ímpar, respectivamente.
- $$c_{0}, c_{1}$$ o número de chaves com id par e ímpar, respectivamente.
Com $$c_{0}$$ baús de id par e $$k_{1}$$ chaves de id ímpar, você pode destrancar no máximo $$min(c_{0}, k_{1})$$ baús.
Com $$c_{1}$$ baús de id ímpar e $$k_{0}$$ chaves de id par, você pode destrancar no máximo $$min(c_{1}, k_{0})$$ baús.
Então, a resposta final é $$min(c_{0}, k_{1}) + min(c_{1}, k_{0})$$.
Complexidade: $$\mathcal{O}(n+m)$$.
https://gist.github.com/Rockbet/8af5fa8e1795416287b0c37cd36cc236
Deixe um comentário