Geek está organizando una carrera de bicicletas con N bikers. La velocidad inicial del i -ésimo motociclista se denota por H i Km/hr y la aceleración del i -ésimo motociclista como A i Km/Hr 2 . 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’ kilómetros por hora o más, se activa la alarma de seguridad. La tarea es encontrar el número mínimo de horas después de las cuales se iniciará 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 en la i-ésima hora:
Biker1 = [ 20 40 60 80 100]
Motorista2 = [50 120 190 260 330]
Motorista3 = [20 110 200 290 380].Velocidad inicial en la pista = 0, porque ninguna de las velocidades del motociclista 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.
La alarma comenzará a la 3.ª hora.Entrada: N = 2, M = 60, L = 120, H = {50, 30}, A = {20, 40}
Salida: 3
Enfoque: El problema dado se puede resolver usando la búsqueda binaria usando el hecho de que si las bicicletas tienen una velocidad inicial U y una aceleración uniforme A , entonces la velocidad en cualquier momento se puede encontrar usando la ecuación: (V = U + A*t) y si, en un tiempo t , las condiciones se cumplen, entonces para todo tiempo mayor que t , se cumplirá, por lo que se descarta la mitad derecha del rango hasta encontrar el valor mínimo. Siga los pasos a continuación para resolver el problema:
- Defina una verificación de función (long H[], long A[], long mid, long N, long M, long L) y realice los siguientes pasos:
- Inicialice la variable, diga suma como 0 que almacena la suma de velocidades.
- Itere sobre un rango [0, N] usando la variable i y si el valor de (mid*A[i] + H[i]) es al menos L , luego agregue este valor a la suma .
- Después de realizar los pasos anteriores, devuelva el valor de la suma como resultado.
- Inicialice las variables, digamos bajo como 0 y alto como 10 10 como el rango de la búsqueda binaria de la respuesta y ans como 0 que almacena el número mínimo de horas.
- Iterar hasta bajo <= alto y realizar los siguientes pasos:
- Encuentre el valor de mid como (low + high)/2 .
- Llame a la función check(H, A, mid, N, M, L) y si el valor devuelto por la función es al menos M , actualice el valor de ans como mid . De lo contrario, actualice el valor de high as (mid – 1) .
- De lo contrario, actualice el valor de low como (mid + 1) .
- Después de realizar los pasos anteriores, imprima el valor de ans como el número de horas resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if the value of
// mid as the minimum number of hours
// satisfies the condition
long check(long H[], long A[], long mid,
long N, long M, long L)
{
// Stores the sum of speed
long sum = 0;
// Iterate over the range [0, N]
for (long i = 0; i < N; i++) {
// Find the value of speed
long speed = mid * A[i] + H[i];
// If the bike is considered
// to be fast add it in sum
if (speed >= L) {
sum += speed;
}
}
// Return the resultant sum
return sum;
}
// Function to find the minimum number
// of time required
long buzzTime(long N, long M, long L,
long H[], long A[])
{
// Stores the range of Binary Search
long low = 0, high = 1e10;
// Stores the minimum number of
// time required
long ans = 0;
while (high >= low) {
// Find the value of mid
long mid = low + (high - low) / 2;
// If the mid is the resultant
// speed required
if (check(H, A, mid,
N, M, L)
>= M) {
// Update the ans and high
ans = mid;
high = mid - 1;
}
// Otherwise
else
low = mid + 1;
}
// Return the minimum number of hours
return ans;
}
// Driver Code
int main()
{
long M = 400, L = 120;
long H[] = { 20, 50, 20 };
long A[] = { 20, 70, 90 };
long N = sizeof(A) / sizeof(A[0]);
cout << buzzTime(N, M, L, H, A);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG
{
// Function to check if the value of
// mid as the minimum number of hours
// satisfies the condition
static long check(long H[], long A[], long mid,
long N, long M, long L)
{
// Stores the sum of speed
long sum = 0;
// Iterate over the range [0, N]
for (long i = 0; i < N; i++) {
// Find the value of speed
long speed = mid * A[(int) i] + H[(int) i];
// If the bike is considered
// to be fast add it in sum
if (speed >= L) {
sum += speed;
}
}
// Return the resultant sum
return sum;
}
// Function to find the minimum number
// of time required
static long buzzTime(long N, long M, long L,
long H[], long A[])
{
// Stores the range of Binary Search
long low = 0, high = 100000000;
// Stores the minimum number of
// time required
long ans = 0;
while (high >= low) {
// Find the value of mid
long mid = low + (high - low) / 2;
// If the mid is the resultant
// speed required
if (check(H, A, mid,
N, M, L)
>= M) {
// Update the ans and high
ans = mid;
high = mid - 1;
}
// Otherwise
else
low = mid + 1;
}
// Return the minimum number of hours
return ans;
}
// Driver Code
public static void main (String[] args) {
long M = 400, L = 120;
long H[] = { 20, 50, 20 };
long A[] = { 20, 70, 90 };
long N = A.length;
System.out.println(buzzTime(N, M, L, H, A));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python 3 program for the above approach # Function to check if the value of # mid as the minimum number of hours # satisfies the condition def check(H, A, mid, N, M, L): # Stores the sum of speed sum = 0 # Iterate over the range [0, N] for i in range(N): # Find the value of speed speed = mid * A[i] + H[i] # If the bike is considered # to be fast add it in sum if (speed >= L): sum += speed # Return the resultant sum return sum # Function to find the minimum number # of time required def buzzTime(N, M, L, H, A): # Stores the range of Binary Search low = 0 high = 1e10 # Stores the minimum number of # time required ans = 0 while (high >= low): # Find the value of mid mid = low + (high - low) // 2 # If the mid is the resultant # speed required if (check(H, A, mid, N, M, L) >= M): # Update the ans and high ans = mid high = mid - 1 # Otherwise else: low = mid + 1 # Return the minimum number of hours return int(ans) # Driver Code if __name__ == '__main__': M = 400 L = 120 H = [20, 50, 20] A = [20, 70, 90] N = len(A) print(buzzTime(N, M, L, H, A)) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if the value of
// mid as the minimum number of hours
// satisfies the condition
static long check(long []H, long []A, long mid,
long N, long M, long L)
{
// Stores the sum of speed
long sum = 0;
// Iterate over the range [0, N]
for(long i = 0; i < N; i++)
{
// Find the value of speed
long speed = mid * A[(int) i] + H[(int) i];
// If the bike is considered
// to be fast add it in sum
if (speed >= L)
{
sum += speed;
}
}
// Return the resultant sum
return sum;
}
// Function to find the minimum number
// of time required
static long buzzTime(long N, long M, long L,
long []H, long []A)
{
// Stores the range of Binary Search
long low = 0, high = 100000000;
// Stores the minimum number of
// time required
long ans = 0;
while (high >= low)
{
// Find the value of mid
long mid = low + (high - low) / 2;
// If the mid is the resultant
// speed required
if (check(H, A, mid, N, M, L) >= M)
{
// Update the ans and high
ans = mid;
high = mid - 1;
}
// Otherwise
else
low = mid + 1;
}
// Return the minimum number of hours
return ans;
}
// Driver Code
public static void Main(String[] args)
{
long M = 400, L = 120;
long []H = { 20, 50, 20 };
long []A = { 20, 70, 90 };
long N = A.Length;
Console.Write(buzzTime(N, M, L, H, A));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript program for the above approach
// Function to check if the value of
// mid as the minimum number of hours
// satisfies the condition
function check(H, A, mid, N, M, L)
{
// Stores the sum of speed
let sum = 0;
// Iterate over the range [0, N]
for (let i = 0; i < N; i++) {
// Find the value of speed
let speed = mid * A[i] + H[i];
// If the bike is considered
// to be fast add it in sum
if (speed >= L) {
sum += speed;
}
}
// Return the resultant sum
return sum;
}
// Function to find the minimum number
// of time required
function buzzTime(N, M, L, H, A)
{
// Stores the range of Binary Search
let low = 0, high = 1e10;
// Stores the minimum number of
// time required
let ans = 0;
while (high >= low) {
// Find the value of mid
let mid = Math.floor(low + (high - low) / 2);
// If the mid is the resultant
// speed required
if (check(H, A, mid, N, M, L)
>= M) {
// Update the ans and high
ans = mid;
high = mid - 1;
}
// Otherwise
else
low = mid + 1;
}
// Return the minimum number of hours
return ans;
}
// Driver Code
let M = 400, L = 120;
let H = [ 20, 50, 20 ];
let A = [ 20, 70, 90 ];
let N = A.length;
document.write(buzzTime(N, M, L, H, A));
// This code is contributed by _saurabh_jaiswal.
</script>
3
Complejidad de tiempo: O(N*log(max(L, M)))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sooryavanshi1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA