Considere n máquinas que producen el mismo tipo de artículos pero a un ritmo diferente, es decir, la máquina 1 tarda 1 segundo en producir un artículo, la máquina 2 tarda 2 segundos en producir un artículo. Dada una array que contiene el tiempo requerido por la i- ésima máquina para producir un artículo. Considerando que todas las máquinas están trabajando simultáneamente, la tarea es encontrar el tiempo mínimo requerido para producir m artículos.
Ejemplos:
Input : arr[] = {1, 2, 3}, m = 11
Output : 6
In 6 sec, machine 1 produces 6 items, machine 2 produces 3 items,
and machine 3 produces 2 items. So to produce 11 items minimum
6 sec are required.
Input : arr[] = {5, 6}, m = 11
Output : 30
Método 1: (Fuerza bruta)
Inicialice el tiempo = 0 e increméntelo en 1. Calcule el número de artículos producidos en cada momento hasta que el número de artículos producidos no sea igual a m.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to find minimum time
// required to produce m items.
#include<bits/stdc++.h>
using namespace std;
// Return the minimum time required to
// produce m items with given machines.
int minTime(int arr[], int n, int m)
{
// Initialize time, items equal to 0.
int t = 0;
while (1)
{
int items = 0;
// Calculating items at each second
for (int i = 0; i < n; i++)
items += (t / arr[i]);
// If items equal to m return time.
if (items >= m)
return t;
t++; // Increment time
}
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3 };
int n = sizeof(arr)/sizeof(arr[0]);
int m = 11;
cout << minTime(arr, n, m) << endl;
return 0;
}
Java
// Java program to find minimum time
// required to produce m items.
import java.io.*;
public class GFG{
// Return the minimum time required to
// produce m items with given machines.
static int minTime(int []arr, int n,
int m)
{
// Initialize time, items equal to 0.
int t = 0;
while (true)
{
int items = 0;
// Calculating items at each second
for (int i = 0; i < n; i++)
items += (t / arr[i]);
// If items equal to m return time.
if (items >= m)
return t;
t++; // Increment time
}
}
// Driver Code
static public void main (String[] args)
{
int []arr = { 1, 2, 3 };
int n = arr.length;
int m = 11;
System.out.println(minTime(arr, n, m));
}
}
// This code is contributed by vt_m.
Python3
# Python3 program to find minimum time # required to produce m items. import math as mt # Return the minimum time required to # produce m items with given machines. def minTime(arr, n, m): # Initialize time, items equal to 0. t = 0 while (1): items = 0 # Calculating items at each second for i in range(n): items += (t // arr[i]) # If items equal to m return time. if (items >= m): return t t += 1 # Increment time # Driver Code arr = [1, 2, 3] n = len(arr) m = 11 print(minTime(arr, n, m) ) # This code is contributed by # Mohit kumar 29
C#
// C# program to find minimum time
// required to produce m items.
using System;
public class GFG{
// Return the minimum time
// required to produce m
// items with given machines.
static int minTime(int []arr, int n,
int m)
{
// Initialize time, items equal to 0.
int t = 0;
while (true)
{
int items = 0;
// Calculating items at each second
for (int i = 0; i < n; i++)
items += (t / arr[i]);
// If items equal to m return time.
if (items >= m)
return t;
t++; // Increment time
}
}
// Driven Code
static public void Main (String []args)
{
int []arr = {1, 2, 3};
int n = arr.Length;
int m = 11;
// Calling function
Console.WriteLine(minTime(arr, n, m));
}
}
PHP
<?php
// PHP program to find minimum time
// required to produce m items.
// Return the minimum time required to
// produce m items with given machines.
function minTime($arr, $n, $m)
{
// Initialize time, items
// equal to 0.
$t = 0;
while (1)
{
$items = 0;
// Calculating items at each second
for ( $i = 0; $i < $n; $i++)
$items += ($t / $arr[$i]);
// If items equal to m return time.
if ($items >= $m)
return $t;
$t++; // Increment time
}
}
// Driver Code
$arr = array(1, 2, 3);
$n =count($arr);
$m = 11;
echo minTime($arr, $n, $m);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript program to find minimum time
// required to produce m items.
// Return the minimum time required to
// produce m items with given machines.
function minTime(arr, n, m)
{
// Initialize time, items equal to 0.
let t = 0;
while (true)
{
let items = 0;
// Calculating items at each second
for (let i = 0; i < n; i++)
items += (t / arr[i]);
// If items equal to m return time.
if (items >= m)
return t;
t++; // Increment time
}
}
// Driver Code
let arr = [ 1, 2, 3 ];
let n = arr.length;
let m = 11;
document.write(minTime(arr, n, m));
</script>
Producción:
6
Método 2 (eficiente):
La idea es utilizar Binary Search . El tiempo máximo posible requerido para producir m elementos será el tiempo máximo en la array, a max , multiplicado por m ie a max * m . Por lo tanto, use la búsqueda binaria entre 1 y un máximo * m y encuentre el tiempo mínimo que produce m elementos.
A continuación se muestra la implementación de la idea anterior:
C++
// Efficient C++ program to find minimum time
// required to produce m items.
#include<bits/stdc++.h>
using namespace std;
// Return the number of items can be
// produced in temp sec.
int findItems(int arr[], int n, int temp)
{
int ans = 0;
for (int i = 0; i < n; i++)
ans += (temp/arr[i]);
return ans;
}
// Binary search to find minimum time required
// to produce M items.
int bs(int arr[], int n, int m, int high)
{
int low = 1;
// Doing binary search to find minimum
// time.
while (low < high)
{
// Finding the middle value.
int mid = (low+high)>>1;
// Calculate number of items to
// be produce in mid sec.
int itm = findItems(arr, n, mid);
// If items produce is less than
// required, set low = mid + 1.
if (itm < m)
low = mid+1;
// Else set high = mid.
else
high = mid;
}
return high;
}
// Return the minimum time required to
// produce m items with given machine.
int minTime(int arr[], int n, int m)
{
int maxval = INT_MIN;
// Finding the maximum time in the array.
for (int i = 0; i < n; i++)
maxval = max(maxval, arr[i]);
return bs(arr, n, m, maxval*m);
}
// Driven Program
int main()
{
int arr[] = { 1, 2, 3 };
int n = sizeof(arr)/sizeof(arr[0]);
int m = 11;
cout << minTime(arr, n, m) << endl;
return 0;
}
Java
// Efficient Java program to find
// minimum time required to
// produce m items.
import java.io.*;
public class GFG{
// Return the number of items can
// be produced in temp sec.
static int findItems(int []arr, int n,
int temp)
{
int ans = 0;
for (int i = 0; i < n; i++)
ans += (temp / arr[i]);
return ans;
}
// Binary search to find minimum time
// required to produce M items.
static int bs(int []arr, int n,
int m, int high)
{
int low = 1;
// Doing binary search to
// find minimum time.
while (low < high)
{
// Finding the middle value.
int mid = (low + high) >> 1;
// Calculate number of items to
// be produce in mid sec.
int itm = findItems(arr, n, mid);
// If items produce is less than
// required, set low = mid + 1.
if (itm < m)
low = mid + 1;
// Else set high = mid.
else
high = mid;
}
return high;
}
// Return the minimum time required to
// produce m items with given machine.
static int minTime(int []arr, int n,
int m)
{
int maxval = Integer.MIN_VALUE;
// Finding the maximum time in the array.
for (int i = 0; i < n; i++)
maxval = Math.max(maxval, arr[i]);
return bs(arr, n, m, maxval * m);
}
// Driven Program
static public void main (String[] args)
{
int []arr = {1, 2, 3};
int n = arr.length;
int m = 11;
System.out.println(minTime(arr, n, m));
}
}
// This code is contributed by vt_m.
Python3
# Efficient Python3 program to find # minimum time required to produce m items. import sys def findItems(arr, n, temp): ans = 0 for i in range(n): ans += temp // arr[i] return ans # Binary search to find minimum time # required to produce M items. def bs(arr, n, m, high): low = 1 # Doing binary search to find minimum # time. while low < high: # Finding the middle value. mid = (low + high) >> 1 # Calculate number of items to # be produce in mid sec. itm = findItems(arr, n, mid) # If items produce is less than # required, set low = mid + 1. if itm < m: low = mid + 1 # Else set high = mid. else: high = mid return high # Return the minimum time required to # produce m items with given machine. def minTime(arr, n, m): maxval = -sys.maxsize # Finding the maximum time in the array. for i in range(n): maxval = max(maxval, arr[i]) return bs(arr, n, m, maxval * m) # Driver Code if __name__ == "__main__": arr = [1, 2, 3] n = len(arr) m = 11 print(minTime(arr, n, m)) # This code is contributed by # sanjeev2552
C#
// Efficient C# program to find
// minimum time required to
// produce m items.
using System;
public class GFG{
// Return the number of items can
// be produced in temp sec.
static int findItems(int []arr, int n,
int temp)
{
int ans = 0;
for (int i = 0; i < n; i++)
ans += (temp / arr[i]);
return ans;
}
// Binary search to find minimum time
// required to produce M items..
static int bs(int []arr, int n,
int m, int high)
{
int low = 1;
// Doing binary search to
// find minimum time.
while (low < high)
{
// Finding the middle value.
int mid = (low + high) >> 1;
// Calculate number of items to
// be produce in mid sec.
int itm = findItems(arr, n, mid);
// If items produce is less than
// required, set low = mid + 1.
if (itm < m)
low = mid + 1;
// Else set high = mid.
else
high = mid;
}
return high;
}
// Return the minimum time required to
// produce m items with given machine.
static int minTime(int []arr, int n,
int m)
{
int maxval = int.MinValue;
// Finding the maximum time in the array.
for (int i = 0; i < n; i++)
maxval = Math.Max(maxval, arr[i]);
return bs(arr, n, m, maxval * m);
}
// Driver Code
static public void Main ()
{
int []arr = {1, 2, 3};
int n = arr.Length;
int m = 11;
Console.WriteLine(minTime(arr, n, m));
}
}
// This code is contributed by vt_m.
PHP
<?php
// Efficient PHP program to find minimum
// time required to produce m items.
// Return the number of items can be
// produced in temp sec.
function findItems( $arr, $n, $temp)
{
$ans = 0;
for($i = 0; $i < $n; $i++)
$ans += ($temp / $arr[$i]);
return $ans;
}
// Binary search to find minimum
// time required to produce M items.
function bs($arr, $n, $m, $high)
{
$low = 1;
// Doing binary search to
// find minimum time.
while ($low < $high)
{
// Finding the middle value.
$mid = ($low + $high) >> 1;
// Calculate number of items to
// be produce in mid sec.
$itm = findItems($arr, $n, $mid);
// If items produce is less than
// required, set low = mid + 1.
if ($itm < $m)
$low = $mid + 1;
// Else set high = mid.
else
$high = $mid;
}
return $high;
}
// Return the minimum time required to
// produce m items with given machine.
function minTime($arr, $n, $m)
{
$maxval = PHP_INT_MIN;
// Finding the maximum
// time in the array.
for($i = 0; $i < $n; $i++)
$maxval = max($maxval, $arr[$i]);
return bs($arr, $n, $m, $maxval*$m);
}
// Driver Code
$arr = array(1, 2, 3);
$n = count($arr);
$m = 11;
echo minTime($arr, $n, $m);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Efficient Javascript program to find
// minimum time required to
// produce m items.
// Return the number of items can
// be produced in temp sec.
function findItems(arr,n,temp)
{
let ans = 0;
for (let i = 0; i < n; i++)
ans += Math.floor(temp / arr[i]);
return ans;
}
// Binary search to find minimum time
// required to produce M items.
function bs(arr,n,m,high)
{
let low = 1;
// Doing binary search to
// find minimum time.
while (low < high)
{
// Finding the middle value.
let mid = (low + high) >> 1;
// Calculate number of items to
// be produce in mid sec.
let itm = findItems(arr, n, mid);
// If items produce is less than
// required, set low = mid + 1.
if (itm < m)
low = mid + 1;
// Else set high = mid.
else
high = mid;
}
return high;
}
// Return the minimum time required to
// produce m items with given machine.
function minTime(arr,n,m)
{
let maxval = Number.MIN_VALUE;
// Finding the maximum time in the array.
for (let i = 0; i < n; i++)
maxval = Math.max(maxval, arr[i]);
return bs(arr, n, m, maxval * m);
}
// Driven Program
let arr=[1, 2, 3];
let n = arr.length;
let m = 11;
document.write(minTime(arr, n, m));
// This code is contributed by patel2127
</script>
Producción:
6
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA