6
He estado intentando this problema en spoj, no he podido encontrar el enfoque correcto. ¿Cuál es el algoritmo correcto para resolver el problema?Número mínimo de operaciones para hacer una matriz ordenada
A
Respuesta
8
Debe encontrar la subsecuencia de incremento consecutiva más larga, que se puede hacer en O (n log n) (ordenando matriz), después de eso, el número de cambios necesarios es N - longest consecutive increasing subsequence. Tenga en cuenta que por consecutivos me refiero a ordenar en matriz ordenada.
por ejemplo:
1 7 6 2 5 4 3 => 1-2-3 es la más larga subsecuencia aumento consecutivo, número de movimientos necesarios es 4.
1 6 4 3 5 2 7 => 1-2 o 4-5 o 6-7 es más larga consecutivos aumentando subsecuencia, tenga en cuenta que el aumento de 1-4-5-7 es más larga subsecuencia pero número de movimientos necesaria es de 5 no 3.
Por qué esto funciona:
mejor algoritmo no cambia algunos de los artículos a los lugares, llame a mayor subsecuencia sin cambios como X, usted no cambia la posición del X elementos relacionados entre sí durante las operaciones, por lo que debe clasificarse en el modo de aumentar. Pero debido a que solo permite mover algunos elementos en la primera o la última matriz, no puede colocar ningún elemento entre X elementos (tenga en cuenta que supusimos que X es la subsecuencia sin cambios más grande durante las operaciones), por lo que no debe haber espacio entre X artículos. por lo tanto, deben ser ordenados y consecutivos en formato ordenado.
El número de cambios necesarios no puede ser menor que el N- length of X, pero tampoco es difícil hacer su trabajo con N-length of X operation.
Cuestiones relacionadas
- 1. Convertir matriz a una ordenada utilizando sólo dos operaciones
- 2. Ordenar una matriz con un número mínimo de comparaciones
- 3. ¿Cómo ordenar una matriz con el mínimo número de escrituras?
- 4. Encontrar el número único mínimo en una matriz
- 5. ¿Es una matriz ordenada un min-heap? ¿Cuál es el valor mínimo de un montón máximo?
- 6. ¿Cómo buscar eficientemente en una matriz ordenada?
- 7. cómo convertir una cadena en un palíndromo con un número mínimo de operaciones?
- 8. Encontrar el número mínimo de operaciones requeridas para calcular un número usando un rango de números especificado
- 9. Manteniendo una matriz ordenada en PHP
- 10. Insertar Perl en una matriz ordenada
- 11. ¿Qué es una matriz ordenada circularmente?
- 12. mínimo de la SED número
- 13. Obtenga los índices originales de una matriz Numpy ordenada
- 14. ¿Encontrar el mínimo de una matriz usando la recursión?
- 15. Número aproximado de ciclos de CPU para varias operaciones
- 16. Dado una serie de bolas rojas y azules, busque el número mínimo de intercambios para agrupar los colores juntos
- 17. Encuentra todos los pares (x, y) en una matriz ordenada para que x + y <z
- 18. número mínimo de hilos de GPU para ser eficaz
- 19. Configuración del número mínimo de decimales para std :: ostream precision
- 20. matriz java para ordenar: forma rápida de obtener una lista ordenada de los índices de una matriz
- 21. encontrar la mediana con el mínimo tiempo de una matriz
- 22. Creación de una lista ordenada al azar de una lista ordenada
- 23. Hacer una matriz de entradas aleatorias
- 24. Mejorando el rendimiento de las operaciones en una matriz NumPy
- 25. Cuál es la forma más eficiente de hacer operaciones bit a bit en una matriz C
- 26. Operaciones rápidas de matriz de JavaScript
- 27. Diseño de una estructura de datos para apoyar operaciones de la pila y para encontrar mínimo pregunta
- 28. ¿Cómo hacer que MATLAB muestre el índice del valor mínimo en una matriz 2D?
- 29. Encuentre el valor mínimo distinto de cero en una matriz
- 30. Operaciones de matriz dispersa en CUDA
Por "subsecuencia creciente consecutiva más larga" ¿se refiere a la subsecuencia común más larga de las secuencias ordenadas y ordenadas? – dasblinkenlight
@dasblinkenlight, no lo que mencionaste es la subsecuencia de mayor aumento, mi inglés no es lo suficientemente bueno y no sé cómo explicarlo bien, traté de ilustrarlo con una muestra, por ejemplo en '1 6 4 3 5 2 7 'lo que dije es' 1, 2', pero la subsecuencia de aumento más larga es '1, 4, 5, 7', si no está claro dígame que lo describa, y si comprende lo que quiero decir, siéntase libre de editar mi respuesta para aclararlo –