Nome: Escalonamento ótimo
Link: http://br.spoj.pl/problems/ESCALO11/
Dificuldade: 9/10
Linguagem: C++
Tempo atingido: 4.31
Memória usada: 5.1M
Colocação alcançada: 22
Tentativas: Várias
Comentário:
Ufa, eu não menti pra vocês, faz mais de uma semana que eu estava tentando resolver este exercício.
Tentei de inúmeras maneiras, utilizei de todas as cartas que eu tinha na manga, e só hoje eu vi a dica de um amigo e descobri uma maneira de fazê-lo passar.
O problema sempre esteve no tempo limite, visto que a quantidade de números e de ligações é enorme.
Pra resolver eu estudei um algoritmo chamado fila de prioridade com heap, onde você cria uma lista e vai eliminando os itens que tem menor prioridade. Sempre que um é eliminado, você reorganiza a fila e verifica se estão eliminação permitiu que mais itens entrassem nela. É um pouco complicado mas dá pra fazer.
Eu recomendo pra quem tem certa experiência.
Dicas:
- Estudem fila de prioridade heap, assim como heap sort.
- Organizem a fila com os itens que não nenhuma dependência, e também aqueles em que a depência já foi resolvida.
Nenhum comentário:
Postar um comentário