Минимальное время, необходимое для производства m изделий

Опубликовано: 20 Января, 2022

Рассмотрим n машин, которые производят предметы одного типа, но с разной скоростью, например, машине 1 требуется ₁ секунда для производства предмета, машине 2 требуется ₂ секунды, чтобы произвести предмет. Дан массив, который содержит время, необходимое i- ^й машине для производства элемента. Учитывая, что все машины работают одновременно, задача состоит в том, чтобы найти минимальное время, необходимое для производства m изделий.
Примеры:

 Ввод: arr [] = {1, 2, 3}, m = 11
Выход: 6
За 6 секунд машина 1 производит 6 единиц, машина 2 производит 3 единицы,
а машина 3 производит 2 единицы. Таким образом, для производства минимум 11 наименований
Требуется 6 сек.

Ввод: arr [] = {5, 6}, m = 11
Выход: 30

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Method 1 : (Brute Force)
Initialize time = 0 and increment it by 1. Calculate number of item produce at each time until number of produced items is not equal to m.
Below is the implementation of the above idea :

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)
{
    // Intialise 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)
{
     
    // Intialise 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.

Python

# 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):
 
    # Intialise 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)
{
     
    // Intialise 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)
{
     
    // Intialise 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)
{
      
    // Intialise 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>

Выход:

Method 2 (efficient):
The idea is to use Binary Search. Maximum possible time required to produce m items will be maximum time in the array, a_max, multiplied by m i.e a_max * m. So, use binary search between 1 to a_max * m and find the minimum time which produce m items.
Below is the implementation of the above idea :

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.

Python

# 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.

                    
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИ
                                    