Dada una array arr[] de tamaño N , que inicialmente consta de 0 s y un entero positivo K , la tarea es imprimir los elementos de la array realizando las siguientes operaciones exactamente K veces.
- Para cada i -ésima operación, seleccione el subarreglo más largo más a la derecha que consiste en todos los 0 y reemplace el elemento medio del subarreglo por i .
- Si existen dos elementos intermedios, compruebe si i es un número par o no . Si se determina que es cierto, reemplace el elemento central más a la derecha con i .
- De lo contrario, reemplace el elemento central más a la izquierda con i .
- Inicialice una cola de prioridad , digamos pq , para almacenar los subarreglos de la forma {X, Y} donde X denota la longitud del subarreglo e Y denota el índice inicial del subarreglo .
- Inicialmente, la longitud máxima del subarreglo con todos los 0 es N y el índice de inicio del subarreglo es 0 . Por lo tanto, inserte { N, 0 } en pq .
- Iterar sobre el rango [1, K] usando la variable i . Para cada i -ésima operación, extraiga el elemento superior de pq y verifique si la longitud del elemento extraído es un número impar o no. Si se determina que es cierto, reemplace el elemento medio del subarreglo con i .
- De lo contrario, si i es un número par , reemplace el elemento medio más a la derecha del subarreglo con i . De lo contrario, reemplace el elemento medio más a la izquierda del subarreglo con i .
- Después de reemplazar el elemento medio con i , inserte la mitad izquierda del subarreglo y la mitad derecha del subarreglo que contiene todos los 0 en pq .
- Finalmente, imprima los elementos de la array.
Ejemplos:
Entrada: arr[] = { 0, 0, 0, 0, 0}, K = 3
Salida: 3 0 1 0 2
Explicación:
En la 1ª operación seleccionando el subarreglo { arr[0], …, arr[4]} y reemplazando arr[2] por 1 modifica arr[] a { 0, 0, 1, 0, 0}
En la segunda operación seleccionando el subarreglo { arr[3], …, arr[4]} y reemplazando arr[4] por 2 modifica arr[] a { 0, 0, 1, 0, 2}
En la tercera operación seleccionando el subarreglo { arr[0], …, arr[1]} y reemplazando arr[1] por 3 modifica arr[] a { 0 , 3, 1, 0, 2}
Por lo tanto, la salida requerida es 3 0 1 0 2.Entrada: arr[] = { 0, 0, 0, 0, 0, 0, 0 }, K = 7
Salida: 7 3 6 1 5 2 4
Enfoque: El problema se puede resolver usando la técnica Greedy . La idea es usar la cola de prioridad para seleccionar el subarreglo más largo más a la derecha con todos los 0. Siga los pasos a continuación para resolver el problema:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement// the above approach #include <bits/stdc++.h>using namespace std; // Function to print array by replacing the mid// of the righmost longest subarray with count// of operations performed on the array void ReplaceArray(int arr[], int N, int K){ // Stores subarray of the form { X, Y }, // where X is the length and Y is start // index of the subarray priority_queue<vector<int> > pq; // Insert the array arr[] pq.push({ N, 0 }); // Stores index of mid // element of the subarray int mid; // Iterate over the range [1, N] for (int i = 1; i <= K; i++) { // Stores top element of pq vector<int> sub = pq.top(); // Pop top element of pq pq.pop(); // If length of the subarray // is an odd number if (sub[0] % 2 == 1) { // Update mid mid = sub[1] + sub[0] / 2; // Replacing arr[mid] with i arr[mid] = i; // Insert left half of // the subarray into pq pq.push({ sub[0] / 2, sub[1] }); // Insert right half of // the subarray into pq pq.push({ sub[0] / 2, (mid + 1) }); } // If length of the current // subarray is an even number else { // If i is // an odd number if (i % 2 == 1) { // Update mid mid = sub[1] + sub[0] / 2; // Replacing mid element // with i arr[mid - 1] = i; // Insert left half of // the subarray into pq pq.push({ sub[0] / 2 - 1, sub[1] }); // Insert right half of // the subarray into pq pq.push({ sub[0] / 2, mid }); } // If i is an even number else { // Update mid mid = sub[1] + sub[0] / 2; // Replacing mid element // with i arr[mid - 1] = i; // Insert left half of // the subarray into pq pq.push({ sub[0] / 2, sub[1] }); // Insert right half of // the subarray into pq pq.push({ sub[0] / 2 - 1, (mid + 1) }); } } } // Print array elements for (int i = 0; i < N; i++) cout << arr[i] << " ";} // Driver Codeint main(){ int arr[] = { 0, 0, 0, 0, 0 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 3; ReplaceArray(arr, N, K);} |
3 0 1 2 0
Complejidad de tiempo: O(K * log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA