carreras de bicicletas

Se está organizando una carrera de bicicletas con N bikers. La velocidad inicial y la aceleración de los ciclistas se dan en las arrays H[] y A[] respectivamente. Un ciclista cuya velocidad es L o más se considera un ciclista rápido. La velocidad total en la pista por cada hora se calcula sumando la velocidad de cada ciclista rápido en esa hora. Cuando la velocidad total en la pista es de M km/hora o más, la alarma de seguridad se activa. La tarea es encontrar el número mínimo de horas después de las cuales se activará la alarma de seguridad.

Ejemplos:

Entrada: N = 3, M = 400, L = 120, H = {20, 50, 20}, A = {20, 70, 90}
Salida: 3
Explicación: Velocidades de todos los Bikers después de cada hora a partir de 0
Biker1 = [20 40 60 80 100] 
Biker2 = [50 120 190 260 330]
Biker3 = [20 110 200 290 380]
Velocidad inicial en la pista = 0 
porque ninguna de las velocidades del ciclista es lo suficientemente rápida.
Velocidad en pista después de la 1.ª hora= 120
Velocidad en pista después de la 2.ª hora= 190+200=390
Velocidad en pista después de la 3.ª hora= 260+290=550
La alarma se activará a la 3.ª hora.

Entrada: N = 2, M = 60, L = 120, H = {50, 30}, A = {20, 40}
Salida: 2

Enfoque ingenuo: un enfoque simple es calcular la velocidad de cada bicicleta en cada hora a partir de la ^hora 0 . Cuando la velocidad total en la pista es de al menos M km/h, ese es el tiempo mínimo en que se activará la alarma.

Complejidad de tiempo: O(N * max(L, M))
Espacio auxiliar:  O(1)

Enfoque eficiente: el problema se puede resolver con la ayuda de la búsqueda binaria en función de la siguiente observación: 

Se puede observar que si en la i ^-ésima hora la velocidad total en la pista es mayor o igual a M , entonces en la (i+1) ^-ésima hora también cumplirá la condición ya que la velocidad de las bicicletas aumenta linealmente con el tiempo.

Siga los pasos mencionados a continuación para implementar la idea anterior:

• Encuentre las horas máximas y mínimas requeridas para encender la alarma porque se utilizarán como valores extremos para la búsqueda binaria.
• Los valores máximo y mínimo serán max(L, M) y 0 respectivamente.
• Use la búsqueda binaria en este rango de tiempo y en cada iteración haga lo siguiente:
  • Iterar de i = 0 a N:
    • Encuentre la velocidad del ciclista en ese momento.
    • Si la velocidad del ciclista en ese momento es al menos L, entonces agregue su velocidad a la velocidad de la pista.
  • Si la velocidad de la pista es al menos M, busque en la mitad izquierda del intervalo de tiempo. De lo contrario, busque en la mitad derecha.
• Devuelve el tiempo mínimo como respuesta.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum required time
// for the alarm to turn on
long buzzTime(long N, long M, long L,
              long H[], long A[])
{
    long l = 0, r = 0, mid, sum = 0;
    long x = max(M, L);
 
    // Loop to find the maximum possible time
    for (long i = 0; i < N; i++) {
        if ((x - H[i]) % A[i] == 0)
            r = max(r, (x - H[i]) / A[i]);
        else
            r = max(r, (x - H[i]) / A[i] + 1);
    }
 
    // Loop to implement binary search
    while (l <= r) {
        mid = (l + r) / 2;
        sum = 0;
 
        // Loop to calculate the speed of
        // each bike at that time
        for (long i = 0; i < N; i++)
            if ((H[i] + A[i] * mid) >= L)
                sum += (H[i] + A[i] * mid);
 
        // Check if the speed of the track
        // is at least M
        if (sum >= M)
            r = mid - 1;
        else
            l = mid + 1;
    }
 
    // Return the minimum time required
    return l;
}
 
// Driver code
int main()
{
    long L = 120, M = 400;
    long H[] = { 20, 50, 20 };
    long A[] = { 20, 70, 90 };
    long N = sizeof(H) / sizeof(H[0]);
 
    // Function call
    long minHour = buzzTime(N, M, L, H, A);
    cout << minHour;
    return 0;
}

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
    // Java code to implement the approach
 
// Function to find the minimum required time
// for the alarm to turn on
static long buzzTime(long N, long M, long L,
              long H[], long A[])
{
    long l = 0, r = 0, mid, sum = 0;
    long x = Math.max(M, L);
 
    // Loop to find the maximum possible time
    for (int i = 0; i < N; i++) {
        if ((x - H[i]) % A[i] == 0)
            r = Math.max(r, (x - H[i]) / A[i]);
        else
            r = Math.max(r, (x - H[i]) / A[i] + 1);
    }
 
    // Loop to implement binary search
    while (l <= r) {
        mid = (l + r) / 2;
        sum = 0;
 
        // Loop to calculate the speed of
        // each bike at that time
        for (int i = 0; i < N; i++)
            if ((H[i] + A[i] * mid) >= L)
                sum += (H[i] + A[i] * mid);
 
        // Check if the speed of the track
        // is at least M
        if (sum >= M)
            r = mid - 1;
        else
            l = mid + 1;
    }
 
    // Return the minimum time required
    return l;
}
 
// Driver Code
public static void main(String args[])
{
    long L = 120, M = 400;
    long H[] = { 20, 50, 20 };
    long A[] = { 20, 70, 90 };
    long N = H.length;
 
    // Function call
    long minHour = buzzTime(N, M, L, H, A);
    System.out.println(minHour);
}
}
 
// This code is contributed by shinjanpatra

# Python3 code to implement the approach
 
# Function to find the minimum required time
# for the alarm to turn on
def buzzTime(N, M, L, H, A) :
 
    l = 0; r = 0; mid=0; sum = 0;
    x = max(M, L);
 
    # Loop to find the maximum possible time
    for i in range(N) :
        if ((x - H[i]) % A[i] == 0) :
            r = max(r, (x - H[i]) / A[i]);
        else :
            r = max(r, (x - H[i]) / A[i] + 1);
 
    # Loop to implement binary search
    while (l <= r) :
        mid = (l + r) // 2;
        sum = 0;
 
        # Loop to calculate the speed of
        # each bike at that time
        for i in range(N) :
            if ((H[i] + A[i] * mid) >= L) :
                sum += (H[i] + A[i] * mid);
 
        # Check if the speed of the track
        # is at least M
        if (sum >= M) :
            r = mid - 1;
        else :
            l = mid + 1;
 
    # Return the minimum time required
    return l;
 
# Driver code
if __name__ == "__main__" :
 
    L = 120; M = 400;
    H = [ 20, 50, 20 ];
    A = [ 20, 70, 90 ];
    N = len(H);
 
    # Function call
    minHour = buzzTime(N, M, L, H, A);
    print(minHour);
 
    # This code is contributed by AnkThon

// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
  // Function to find the minimum required time
  // for the alarm to turn on
  static long buzzTime(long N, long M, long L, long[] H, long[] A)
  {
    long l = 0, r = 0, mid, sum = 0;
    long x = Math.Max(M, L);
 
    // Loop to find the maximum possible time
    for (int i = 0 ; i < N ; i++) {
      if ((x - H[i]) % A[i] == 0)
        r = Math.Max(r, (x - H[i]) / A[i]);
      else
        r = Math.Max(r, (x - H[i]) / A[i] + 1);
    }
 
    // Loop to implement binary search
    while (l <= r) {
      mid = (l + r) / 2;
      sum = 0;
 
      // Loop to calculate the speed of
      // each bike at that time
      for (int i = 0 ; i < N ; i++)
        if ((H[i] + A[i] * mid) >= L){
          sum += (H[i] + A[i] * mid);
        }
 
      // Check if the speed of the track
      // is at least M
      if (sum >= M){
        r = mid - 1;
      }else{
        l = mid + 1;
      }
    }
 
    // Return the minimum time required
    return l;
  }
 
  public static void Main(string[] args){
 
    long L = 120, M = 400;
    long[] H = new long[]{ 20, 50, 20 };
    long[] A = new long[]{ 20, 70, 90 };
    long N = H.Length;
 
    // Function call
    long minHour = buzzTime(N, M, L, H, A);
    Console.WriteLine(minHour);
 
  }
}
 
// This code is contributed by entertain2022.

<script>
        // JavaScript code for the above approach
 
 
        // Function to find the minimum required time
        // for the alarm to turn on
        function buzzTime(N, M, L,
            H, A) {
            let l = 0, r = 0, mid, sum = 0;
            let x = Math.max(M, L);
 
            // Loop to find the maximum possible time
            for (let i = 0; i < N; i++) {
                if ((x - H[i]) % A[i] == 0)
                    r = Math.max(r, (x - H[i]) / A[i]);
                else
                    r = Math.max(r, (x - H[i]) / A[i] + 1);
            }
 
            // Loop to implement binary search
            while (l <= r) {
                mid = Math.floor((l + r) / 2);
                sum = 0;
 
                // Loop to calculate the speed of
                // each bike at that time
                for (let i = 0; i < N; i++)
                    if ((H[i] + A[i] * mid) >= L)
                        sum += (H[i] + A[i] * mid);
 
                // Check if the speed of the track
                // is at least M
                if (sum >= M)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
 
            // Return the minimum time required
            return l;
        }
 
        // Driver code
 
        let L = 120, M = 400;
        let H = [20, 50, 20];
        let A = [20, 70, 90];
        let N = H.length;
 
        // Function call
        let minHour = buzzTime(N, M, L, H, A);
        document.write(minHour);
 
    // This code is contributed by Potta Lokesh
    </script>

3

Complejidad de tiempo: O(N * log(max(L, M)))
Espacio auxiliar: O(1)