Nome: Bolhas e baldes
Link: http://br.spoj.pl/problems/BALDES/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 1.32
Memória usada: 3.4M
Colocação alcançada: 100+
Tentativas: 2
Comentário:
Este exercício parece extremamente simples, porém o tamanho da cadeia de valores faz com que um algoritmo ingênuo estoure o tempo.
Trata-se de mais um exercício de ordenação, com foco na quantidade de trocas realizadas.
Porém a cadeia de até 100mil valores faz com que um simples Bubble Sort estoure o tempo, e o fato de que só são possíveis trocas de valores adjacentes na cadeia faz com que o Quick Sort seja inútil.
Portanto o que nos resta é o Merge Sort, modificado para retornar a quantidade de trocas.
Eu não conhecia o Merge Sort até ontem, e fiquei impressionado com sua complexidade.
Mas pesquisem, vale a pena.
Dicas:
- Estudem o algoritmo Merge Sort e modifiquem-o para retornar a quantidade de trocas.
- Notem que só são possíveis trocas de valores adjacente na cadeia, ou seja, valores que estão lado a lado.
Nenhum comentário:
Postar um comentário