Operaciones mínimas de tipo dado requeridas para vaciar una array dada

Dada una array arr[] de tamaño N , la tarea es encontrar el recuento total de operaciones requeridas para eliminar todos los elementos de la array, de modo que si el primer elemento de la array es el elemento más pequeño , elimine ese elemento; de lo contrario, mueva el primero elemento hasta el final de la array.

Ejemplos:

Entrada: A[] = {8, 5, 2, 3}
Salida: 7
Explicación: Inicialmente, A[] = {8, 5, 2, 3}
Paso 1: 8 no es el más pequeño. Por lo tanto, moverlo al final de la array modifica A[] a {5, 2, 3, 8}.
Paso 2: 5 no es el más pequeño. Por lo tanto, moverlo al final de la array modifica A[] a {2, 3, 8, 5}.
Paso 3: 2 es el más pequeño. Por lo tanto, eliminarlo de la array modifica A[] a {3, 8, 5}
Paso 4: 3 es el más pequeño. Por lo tanto, eliminarlo de la array modifica A[] a A[] = {5, 8}
Paso 6: 5 es el más pequeño. Por lo tanto, eliminarlo de la array modifica A[] a {8}
Paso 7: 8 es el más pequeño. Por lo tanto, eliminarlo de la array modifica A[] a {}
Por lo tanto, se requieren 7 operaciones para eliminar toda la array.

Entrada: A[] = {8, 6, 5, 2, 7, 3, 10}
Salida: 18

Enfoque ingenuo: el enfoque más simple para resolver el problema es verificar repetidamente si el primer elemento de la array es el elemento más pequeño de la array o no. Si se encuentra que es cierto, elimine ese elemento e incremente el conteo. De lo contrario, mueva el primer elemento de la array al final de la array e incremente el conteo. Finalmente, imprima el conteo total obtenido.
Complejidad temporal: O(N ³ )
Espacio auxiliar: O(N)

Enfoque eficiente: el problema se puede resolver de manera eficiente utilizando un enfoque de programación dinámica y un algoritmo de clasificación . Siga los pasos a continuación para resolver el problema:

1. Almacene los elementos de la array A[] con sus índices en un vector de pares, digamos vector a .
2. Ordena el vector según los valores de los elementos.
3. Inicialice las arrays countGreater_right[] y countGreater_left[] para almacenar la cantidad de elementos mayores presentes a la derecha del elemento actual y la cantidad de elementos mayores presentes a la izquierda del elemento actual en la array dada, respectivamente, lo que se puede hacer usando un conjunto estructura de datos
4. Inicialmente, almacene el índice del elemento inicial del vector a como prev = a[0].segundo.
5. Inicializa el conteo con prev+1 .
6. Ahora, atraviese cada elemento del vector a , desde i = 1 hasta N-1 .
7. Para cada elemento, recupere su índice original como ind = a[i].segundo y la transición dp para cada elemento es:

Si ind > prev , incrementa el conteo por countGreater_right[prev] – countGreater_right[ind] , de lo contrario

Incremente el conteo por countGreater_right[prev] + countGreater_left[ind] + 1 .

        8. Después de atravesar, imprima la cuenta como respuesta.

A continuación se muestra la implementación del algoritmo anterior:

// C++ program for the above approach
 
#include
#include
using namespace std;
 
// Function to find the count of greater
// elements to right of each index
void countGreaterRight(int A[], int len,
                       int* countGreater_right)
{
 
    // Store elements of array
    // in sorted order
    multiset s;
 
    // Traverse the array in reverse order
    for (int i = len - 1; i >= 0; i--) {
        auto it = s.lower_bound(A[i]);
 
        // Stores count of greater elements
        // on the right of i
        countGreater_right[i]
            = distance(it, s.end());
 
        // Insert current element
        s.insert(A[i]);
    }
}
 
// Function to find the count of greater
// elements to left of each index
void countGreaterLeft(int A[], int len,
                      int* countGreater_left)
{
 
    // Stores elements in
    // a sorted order
    multiset s;
 
    // Traverse the array
    for (int i = 0; i <= len; i++) {
        auto it = s.lower_bound(A[i]);
 
        // Stores count of greater elements
        // on the left side of i
        countGreater_left[i]
            = distance(it, s.end());
 
        // Insert current element into multiset
        s.insert(A[i]);
    }
}
 
// Function to find the count of operations required
// to remove all the array elements such that If
// 1st elements is smallest then remove the element
// otherwise move the element to the end of array
void cntOfOperations(int N, int A[])
{
    int i;
 
    // Store {A[i], i}
    vector<pair > a;
 
    // Traverse the array
    for (i = 0; i < N; i++) {
 
        // Insert {A[i], i}
        a.push_back(make_pair(A[i], i));
    }
 
    // Sort the vector pair according to
    // elements of the array, A[]
    sort(a.begin(), a.end());
 
    // countGreater_right[i]: Stores count of
    // greater elements on the right side of i
    int countGreater_right[N];
 
    // countGreater_left[i]: Stores count of
    // greater elements on the left side of i
    int countGreater_left[N];
 
    // Function to fill the arrays
    countGreaterRight(A, N, countGreater_right);
    countGreaterLeft(A, N, countGreater_left);
 
    // Index of smallest element
    // in array A[]
    int prev = a[0].second, ind;
 
    // Stores count of greater element
    // on left side of index i
    int count = prev + 1;
 
    // Iterate over remaining elements
    // in of a[][]
    for (i = 1; i  prev) {
 
            // Update count
            count += countGreater_right[prev]
                     - countGreater_right[ind];
        }
 
        else {
 
            // Update count
            count += countGreater_right[prev]
                     + countGreater_left[ind] + 1;
        }
 
        // Update prev
        prev = ind;
    }
 
    // Print count as total number
    // of operations
    cout << count;
}
 
// Driver Code
int main()
{
 
    // Given array
    int A[] = { 8, 5, 2, 3 };
 
    // Given size
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function Call
    cntOfOperations(N, A);
    return 0;
}

# Python3 program for the above approach
from bisect import bisect_left, bisect_right
 
# Function to find the count of greater
# elements to right of each index
def countGreaterRight(A, lenn,countGreater_right):
 
    # Store elements of array
    # in sorted order
    s = {}
 
    # Traverse the array in reverse order
    for i in range(lenn-1, -1, -1):
        it = bisect_left(list(s.keys()), A[i])
 
        # Stores count of greater elements
        # on the right of i
        countGreater_right[i] = it
 
        # Insert current element
        s[A[i]] = 1
    return countGreater_right
 
# Function to find the count of greater
# elements to left of each index
def countGreaterLeft(A, lenn,countGreater_left):
 
    # Store elements of array
    # in sorted order
    s = {}
 
    # Traverse the array in reverse order
    for i in range(lenn):
        it = bisect_left(list(s.keys()), A[i])
 
        # Stores count of greater elements
        # on the right of i
        countGreater_left[i] = it
 
        # Insert current element
        s[A[i]] = 1
    return countGreater_left
 
# Function to find the count of operations required
# to remove all the array elements such that If
# 1st elements is smallest then remove the element
# otherwise move the element to the end of array
def cntOfOperations(N, A):
 
    # Store {A[i], i}
    a = []
 
    # Traverse the array
    for i in range(N):
 
        # Insert {A[i], i}
        a.append([A[i], i])
 
    # Sort the vector pair according to
    # elements of the array, A[]
    a = sorted(a)
 
    # countGreater_right[i]: Stores count of
    # greater elements on the right side of i
    countGreater_right = [0 for i in range(N)]
 
    # countGreater_left[i]: Stores count of
    # greater elements on the left side of i
    countGreater_left = [0 for i in range(N)]
 
    # Function to fill the arrays
    countGreater_right = countGreaterRight(A, N,
                                           countGreater_right)
    countGreater_left = countGreaterLeft(A, N,
                                         countGreater_left)
 
    # Index of smallest element
    # in array A[]
    prev, ind = a[0][1], 0
 
    # Stores count of greater element
    # on left side of index i
    count = prev
 
    # Iterate over remaining elements
    # in of a[][]
    for i in range(N):
 
        # Index of next smaller element
        ind = a[i][1]
 
        # If ind is greater
        if (ind > prev):
 
            # Update count
            count += countGreater_right[prev] - countGreater_right[ind]
 
        else:
            # Update count
            count += countGreater_right[prev] + countGreater_left[ind] + 1
 
        # Update prev
        prev = ind
 
    # Print count as total number
    # of operations
    print (count)
 
# Driver Code
if __name__ == '__main__':
 
    # Given array
    A = [8, 5, 2, 3 ]
 
    # Given size
    N = len(A)
 
    # Function Call
    cntOfOperations(N, A)
 
# This code is contributed by mohit kumar 29

7

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(N)

Nota: El enfoque anterior se puede optimizar encontrando el recuento de elementos mayores en el lado izquierdo y derecho de cada índice usando Fenwick Tree .