Saltar al contenido

Tiempo total para elegir elementos con intervalo de tiempo dado

Dada una matriz Arr[] de tamaño norte que indica el tipo de un elemento, y otra matriz de tiempo hora[] de tamaño norte Donde hora[i] indica el intervalo de tiempo entre la elección de dos elementos de la imi escribe. La tarea es encontrar el tiempo que lleva elegir todos los elementos a medida que se mueve de izquierda a derecha a través de la matriz.

Observación: Moverse entre posiciones adyacentes toma 1 unidad de tiempo y no se necesita tiempo adicional para elegir un elemento. Además, las matrices siguen una indexación basada en 1.

Ejemplos:

Aporte: N = 4, arr = {1, 2, 3, 3}, tiempo = {1, 2, 3, 4}
Salida: 5
Explicación: Empiezas en index1 y eliges Arr[1] es decir, 1 en poco tiempo.
En 1 segundo pasas del índice 1 Hasta que 2y elige arr[2] es decir, 2, tiempo total = 1.
En el próximo 1 segundo, pasas del índice 2 Hasta que 3 y elige arr[3] a saber, 3, tiempo total = 2.
En el próximo 1 segundo, pasas del índice 3 Hasta que 4y Arr[4] es 3que ya has tomado en el tiempo 2, así que tienes que esperar hora[arr[i]] seg para volver a marcar arr[i], hora[arr[i]]= tiempo[3] = 3.
Entonces en 1 segundo te mudaste del índice 3 Hasta que 4esperaba el siguiente 2 seg, y finalmente eligió arr[4]tiempo total = 5.

Aporte: N = 4, arr[] = {1, 2, 3, 4}, tiempo[] = {1, 2, 3, 4}
Salida: 3
Explicación: Todos los elementos de la matriz son diferentes, por lo que no tiene que esperar por un arreglo.[i] entonces, antes de elegirlo, el tiempo total es 3, que es el tiempo que se tarda en recorrer la matriz.

Acercarse: Este problema se puede resolver usando un Algoritmo codicioso y hash.

La idea es iterar sobre la matriz y actualizar la marca de tiempo para cada elemento. Si la diferencia entre la hora actual y la marca de tiempo anterior para el elemento actual es menor que el tiempo de espera, sume el tiempo de espera a la hora actual.

Pasos involucrados en la implementación del enfoque anterior:

  • Inicializar la hora actual como -1.
  • hacer una Tabla de picadillo de tamaño N para almacenar la última marca de tiempo de los N elementos.
  • En cada iteración, aumente el tiempo actual en 1.
  • Compruebe si la diferencia entre la hora actual y la marca de tiempo anterior para el elemento actual es menor que el tiempo de espera y agregue el tiempo de espera a la hora actual.
  • Actualice la marca de tiempo del elemento a la hora actual.

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

C++

 

#include <bits/stdc++.h>

using namespace std;

 

int totalTime(int n, vector<int>& arr, vector<int>& time)

{

    

    int t = -1;

    vector<int> v(n, -1);

 

    for (int i = 0; i < n; i++) {

        t++;

 

        

        

        

        

        if (t - v[arr[i] - 1] < time[arr[i] - 1])

            t += time[arr[i] - 1] - t + v[arr[i] - 1];

 

        v[arr[i] - 1] = t;

    }

    return t;

}

 

int main()

{

    vector<int> arr = { 1, 2, 3, 3 };

    vector<int> time = { 1, 2, 3, 4 };

    int N = arr.size();

 

    

    cout << totalTime(N, arr, time);

 

    return 0;

}

Complejidad del tiempoa: A)
cuarto auxiliar: O(1)

Artículos relacionados: