a [L] … a [R] está casi ordenado si:
a [L] a [L] … a [R-1]
Defina dos matrices para ayudar a resolver el problema de encontrar todos los intervalos casi doloridos en una matriz:
izquierda [i] = j donde j a [i]
derecha [i] = j donde j> i y j está más cerca de i y a [j] <a [i]
Estas matrices ayudan a definir cuándo dos indicaciones i y j forman un intervalo casi ordenado. Para algunos i y j, un [i] … a [j] es un intervalo casi ordenado si j> left [i] e i <right [j].
- ¿Por qué char array proporciona String cuando se imprime en el método System.out.println ()?
- Cómo verificar si un número es un primo retorcido o no usa bucle
- Cómo resolver SPOJ.com - Problema GERGOVIA en SPOJ
- ¿Qué método es el más adecuado para resolver problemas de programación de enfermería, programación dinámica o algoritmos genéticos, y por qué?
- ¿Cuál es la diferencia entre la función de aptitud del algoritmo genético y la función de pérdida del descenso de gradiente?
Para contar el número total de intervalos casi ordenados, iteraremos de derecha a izquierda a través de los índices. Mientras iteramos sobre los índices, mantendremos un conjunto B compuesto de potenciales a [R] contra los cuales necesitamos ver si la corriente a [i] es un intervalo casi ordenado. A medida que iteramos i de N a 1, para cada i único agregamos uno a [i] como A [R] al conjunto B y luego eliminamos esto agregamos un [R] cuando iteramos al índice a la izquierda [R] ( aquí R era el valor de i cuando se agregó).
Después de agregar la a [R], probamos si a [i] como una a [L] válida contra el conjunto de a [R] ‘s en B. Una a [R] en el conjunto B es válida casi ordenada intervalo si es correcto [L]> R. Dado que realizar la prueba solo requiere el valor R para cada a [R] agregado al conjunto, representamos el conjunto de a [R] ‘s agregando los valores R a B (que es solo yo en el momento en que estamos agregando un [i] como un a [R]). Por lo tanto, podemos contar el número de intervalos válidos casi ordenados realizados con una [L] contra los a [R] ‘s en el conjunto B contando el número de valores R en el conjunto B que son inferiores a la derecha [L] (donde L aquí estoy cuando realizo la prueba).
Este recuento del número de valores R en B menos que a la derecha [L] se puede hacer en tiempo O (log N) utilizando el árbol indexado binario. ver Tutoriales de algoritmos.
