dado un Arr[] de enteros positivos y Empezar[] y final[] series de longitud Lque es el índice inicial y final de . contiene yo número de subarreglos que no se intersecan si un inicio[i] y final[i] para todos (1 i ≤ L). Una operación se define de la siguiente manera:
- Seleccione una parte continua o no continua ordenada del subarreglo y luego agregue un número entero, digamos A, a todos los elementos de la parte elegida.
Entonces es tarea de monto minimo de datos ediciones requeridas para distinguir todos los elementos de todos los subarreglos que no se intersecan.
Observación: Si más de un subarreglo contiene el mismo elemento, no importa. Solo cada subarreglo debe contener diferentes elementos por sí mismo.
Ejemplos:
Aporte: Arr[] = {2, 2, 1, 2, 3}, comienzo[] = {1, 3}, fin[] = {2, 5}
Salida: 1
Explicación: Primera sub-matriz: [start[1]final[1]]= {2, 2}.
Segundo subarreglo: [start[3]final[5]]= {1, 2, 3}.
En First Subarray, elija el subarreglo del índice 1 a 1 como {2} y más cualquier número entero, digamos 1. Luego, First Subarray = {3, 2}. Ahora ambos subarreglos contienen diferentes elementos por sí mismos. El número total de operaciones requeridas es 1.Aporte: Arr[] = {1, 2, 3, 3, 4, 5}, empezar[] = {1, 4}, fin[] = {3, 6}
Salida: 0
Explicación: Se puede verificar que los subarreglos {1, 2, 3} y {3, 4, 5} son ambos diferentes en sí mismos. Por lo tanto, el número total de operaciones requeridas es 0.
Acercarse: Implemente la siguiente idea para resolver el problema:
Distinguir todos los elementos. en un subarreglo solo por cierta operación depende de la frecuencia máxima en un subarregloSi hemos convertido el elemento de alta frecuencia en una forma separada, se pueden distinguir al mismo tiempo el resto de frecuencias inferiores a la frecuencia máxima. Para mayor claridad, consulte el enfoque de concepto. Determine la frecuencia máxima en cada subarreglo y aplique el siguiente algoritmo.
Enfoque de comprensión:
Supongamos que nuestro subarreglo A[] es = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2}. La frecuencia más alta aquí es 10.
Primera operación: Elija una subcadena ordenada del índice 6 al 10 y agregue un número entero aleatorio, digamos 1, a todos los elementos de la subsecuencia. Después, A[] = {2, 2, 2, 2, 2, 3, 3, 3, 3, 3}. La frecuencia más alta es 5 hasta aquí.
Segunda operación: Elija una subcadena ordenada del índice 3 al 5 y del 8 al 10 y agregue un número entero aleatorio, digamos 2, a todos los elementos de la subcadena. que un[] = {2, 2, 4, 4, 4, 3, 3, 5, 5, 5}. La frecuencia más alta es 3 hasta aquí.
Tercera operación: Elija un subconjunto ordenado de índice 4 a 5 y 9 a 10 y agregue un número entero aleatorio, digamos 3, a todos los elementos del subconjunto. que un[] = {2, 2, 4, 7, 7, 3, 3, 5, 8, 8}
Cuarta operación: Elija un subconjunto ordenado de índices: {1, 4, 6, 9} agregue cualquier número entero, por ejemplo, 10, a todos los elementos del subconjunto. que un[] = {12, 2, 4, 17, 7, 13, 3, 5, 18, 8}
Asi que, Solo se necesitan cuatro operaciones para convertir a elementos individuales. En la segunda operación, podemos ver que tanto el elemento 2 como el 3 tienen una frecuencia de 5 y los convertimos con éxito en elementos diferentes. Esto nos da la idea de que Si tratamos de hacer distintivo el elemento de máxima frecuencia, entonces el resto de elementos con una frecuencia menor o igual a la frecuencia máxima se pueden convertir simultáneamente en distinguibles.
En el ejemplo anterior se puede ver claramente que, Con cada operación estamos convirtiendo exactamente la mitad del elementos, como valor de max_frequency es par en la operación actual de lo contrario estamos convertir (max_frequency+1)/2 elementos me gusta reducimos el valor de max_frequency de la misma maneraEntonces podemos concluir el siguiente algoritmo para resolver el problema.
Algoritmo para resolver el problema:
1. Crear una variable digamos min_operaciones para almacenar el número total de operaciones mínimas requeridas para todos los subconjuntos.
2. Para cualquier subarreglo dado, siga los pasos a continuación:
- Cuenta la frecuencia de cada elemento y guárdalos en Hash-Map.
- Vaya a través del Hash-Map para obtener la frecuencia máxima en una variable, digamos: frecuencia_máxima.
- Crear e inicializar contador variable a cero.
- Aplique el siguiente algoritmo para obtener el número mínimo de operaciones requeridas.
mientras (frecuencia_máxima > 1)
{
si (es par (max_frequency))
{
frecuencia_máxima/=2;
}
de lo contrario
{
frecuencia_máxima = (frecuencia_máxima+1)/2;
}
contador++;
}
- Al completar el ciclo agregando valor de la variable de contador en min_operations.
3. Después de aplicar el algoritmo anterior a cualquier subarreglo dado: imprime el valor de min_operations.
A continuación se muestra el código para implementar el enfoque:
Java
|
Complejidad del tiempo: A)
cuarto auxiliar: A)