logo

الحد الأدنى من الوقت اللازم لإنتاج عناصر م

منح ن الآلات الممثلة بمصفوفة عددية وصول[] أين وصول [i] يشير إلى الوقت (بالثواني) الذي يستغرقه ط-ال آلة لإنتاج واحد غرض. جميع الآلات تعمل معًا وبشكل مستمر. بالإضافة إلى ذلك، يتم إعطاؤنا أيضًا عددًا صحيحًا م يمثل العدد الإجمالي العناصر المطلوبة . المهمة هي تحديد الحد الأدنى من الوقت اللازمة لإنتاج بالضبط م العناصر بكفاءة.

أمثلة:  

مدخل: آر[] = [2 4 5] م = 7
الإخراج: 8
توضيح: الطريقة الأمثل للإنتاج 7 العناصر في الحد الأدنى الوقت هو 8 ثواني. تنتج كل آلة العناصر بمعدلات مختلفة:



  • الآلة 1 ينتج عنصر كل 2 ثواني → ينتج 8/2 = 4 العناصر في 8 ثواني.
  • الآلة 2 ينتج عنصر كل 4 ثواني → ينتج 8/4 = 2 العناصر في 8 ثواني.
  • الآلة 3 ينتج عنصر كل 5 ثواني → ينتج 8/5 = 1 البند في 8 ثواني.

إجمالي العناصر المنتجة في 8 ثواني = 4 + 2 + 1 = 7


مدخل: آر[] = [2 3 5 7] م = 10
الإخراج: 9
توضيح: الطريقة الأمثل للإنتاج 10 العناصر في الحد الأدنى الوقت هو 9 ثواني. تنتج كل آلة العناصر بمعدلات مختلفة:

  • تنتج الآلة 1 عنصرًا لكل منها 2 ثواني - تنتج 9/2 = 4 العناصر في 9 ثواني.
  • الآلة 2 تنتج عنصرًا كل 3 ثواني - تنتج 9/3 = 3 العناصر في 9 ثواني.
  • تنتج الآلة 3 عنصرًا لكل منها 5 ثواني - تنتج 9/5 = 1 البند في 9 ثواني.
  • تنتج الآلة 4 عنصرًا لكل منها 7 ثواني - تنتج 9/7 = 1 البند في 9 ثواني.

إجمالي العناصر المنتجة في 9 ثواني = 4 + 3 + 1 + 1 = 10

جدول المحتويات

استخدام طريقة القوة الغاشمة - O(n*m*min(arr)) الوقت وO(1) الفضاء

الفكرة هي أن تحقق بشكل متزايد الحد الأدنى من الوقت اللازم لإنتاج بالضبط م أغراض. نبدأ مع الوقت = 1 والاستمرار في زيادتها حتى يصل إجمالي العناصر التي تنتجها جميع الآلات ≥ م . في كل خطوة نقوم بحساب عدد العناصر التي يمكن لكل آلة إنتاجها باستخدامها الوقت / وصول [i] وتلخيصها. وبما أن جميع الآلات تعمل معًا يضمن هذا النهج العثور على أصغر وقت صالح.

C++
// C++ program to find minimum time  // required to produce m items using  // Brute Force Approach #include    using namespace std; int minTimeReq(vector<int> &arr int m) {    // Start checking from time = 1  int time = 1;    while (true) {  int totalItems = 0;  // Calculate total items produced at   // current time  for (int i = 0; i < arr.size(); i++) {  totalItems += time / arr[i];  }  // If we produce at least m items   // return the time  if (totalItems >= m) {  return time;  }  // Otherwise increment time and   // continue checking  time++;  } } int main() {  vector<int> arr = {2 4 5};  int m = 7;  cout << minTimeReq(arr m) << endl;  return 0; } 
Java
// Java program to find minimum time  // required to produce m items using  // Brute Force Approach import java.util.*; class GfG {  static int minTimeReq(int arr[] int m) {    // Start checking from time = 1  int time = 1;    while (true) {  int totalItems = 0;  // Calculate total items produced at   // current time  for (int i = 0; i < arr.length; i++) {  totalItems += time / arr[i];  }  // If we produce at least m items   // return the time  if (totalItems >= m) {  return time;  }  // Otherwise increment time and   // continue checking  time++;  }  }  public static void main(String[] args) {    int arr[] = {2 4 5};  int m = 7;  System.out.println(minTimeReq(arr m));  } } 
Python
# Python program to find minimum time  # required to produce m items using  # Brute Force Approach def minTimeReq(arr m): # Start checking from time = 1 time = 1 while True: totalItems = 0 # Calculate total items produced at  # current time for i in range(len(arr)): totalItems += time // arr[i] # If we produce at least m items  # return the time if totalItems >= m: return time # Otherwise increment time and  # continue checking time += 1 if __name__ == '__main__': arr = [2 4 5] m = 7 print(minTimeReq(arr m)) 
C#
// C# program to find minimum time  // required to produce m items using  // Brute Force Approach using System; class GfG {  static int minTimeReq(int[] arr int m) {    // Start checking from time = 1  int time = 1;    while (true) {  int totalItems = 0;  // Calculate total items produced at   // current time  for (int i = 0; i < arr.Length; i++) {  totalItems += time / arr[i];  }  // If we produce at least m items   // return the time  if (totalItems >= m) {  return time;  }  // Otherwise increment time and   // continue checking  time++;  }  }  public static void Main() {    int[] arr = {2 4 5};  int m = 7;  Console.WriteLine(minTimeReq(arr m));  } } 
JavaScript
// JavaScript program to find minimum time  // required to produce m items using  // Brute Force Approach function minTimeReq(arr m) {    // Start checking from time = 1  let time = 1;    while (true) {  let totalItems = 0;  // Calculate total items produced at   // current time  for (let i = 0; i < arr.length; i++) {  totalItems += Math.floor(time / arr[i]);  }  // If we produce at least m items   // return the time  if (totalItems >= m) {  return time;  }  // Otherwise increment time and   // continue checking  time++;  } } // Input values let arr = [2 4 5]; let m = 7; console.log(minTimeReq(arr m)); 

الإخراج
8 

تعقيد الوقت: O(n*m*min(arr)) لأنه في كل وحدة زمنية (حتى m * min(arr)) نقوم بالتكرار من خلال n آلات لحساب العناصر المنتجة.
تعقيد الفضاء: O(1) حيث يتم استخدام عدد قليل فقط من المتغيرات الصحيحة؛ لم يتم تخصيص أي مساحة إضافية.

استخدام البحث الثنائي - O(n*log(m*min(arr))) Time وO(1) Space

ال فكرة هو الاستخدام البحث الثنائي بدلا من التحقق في كل مرة بالتتابع نلاحظ أن إجمالي الأصناف المنتجة في وقت معين ت يمكن حسابها في على) . الملاحظة الرئيسية هي أن الحد الأدنى من الوقت الممكن هو 1 والحد الأقصى للوقت الممكن هو م * دقيقةMachineTime . عن طريق التقديم البحث الثنائي في هذا النطاق، نتحقق بشكل متكرر من القيمة المتوسطة لتحديد ما إذا كانت كافية ونضبط مساحة البحث وفقًا لذلك.

خطوات تنفيذ الفكرة السابقة:

  • تعيين اليسار إلى 1 و يمين ل م * دقيقةMachineTime لتحديد مساحة البحث.
  • تهيئة الجواب مع يمين لتخزين الحد الأدنى من الوقت المطلوب.
  • تشغيل البحث الثنائي بينما غادر أقل من أو يساوي يمين .
  • احسب منتصف وحساب إجمالي العناصر من خلال التكرار وصول والتلخيص منتصف / وصول [i] .
  • إذا كان إجمالي العناصر على الأقل م تحديث سنين و البحث عن وقت أصغر. وإلا ضبط غادر ل منتصف +1 لوقت أكبر.
  • مواصلة البحث حتى يتم العثور على الحد الأدنى الأمثل من الوقت.
C++
// C++ program to find minimum time  // required to produce m items using  // Binary Search Approach #include    using namespace std; int minTimeReq(vector<int> &arr int m) {    // Find the minimum value in arr manually  int minMachineTime = arr[0];  for (int i = 1; i < arr.size(); i++) {  if (arr[i] < minMachineTime) {  minMachineTime = arr[i];  }  }  // Define the search space  int left = 1;  int right = m * minMachineTime;  int ans = right;    while (left <= right) {    // Calculate mid time  int mid = left + (right - left) / 2;  int totalItems = 0;  // Calculate total items produced in 'mid' time  for (int i = 0; i < arr.size(); i++) {  totalItems += mid / arr[i];  }  // If we can produce at least m items  // update answer  if (totalItems >= m) {  ans = mid;    // Search for smaller time  right = mid - 1;  }   else {    // Search in right half  left = mid + 1;  }  }    return ans; } int main() {    vector<int> arr = {2 4 5};  int m = 7;  cout << minTimeReq(arr m) << endl;  return 0; } 
Java
// Java program to find minimum time  // required to produce m items using  // Binary Search Approach import java.util.*; class GfG {    static int minTimeReq(int[] arr int m) {    // Find the minimum value in arr manually  int minMachineTime = arr[0];  for (int i = 1; i < arr.length; i++) {  if (arr[i] < minMachineTime) {  minMachineTime = arr[i];  }  }  // Define the search space  int left = 1;  int right = m * minMachineTime;  int ans = right;    while (left <= right) {    // Calculate mid time  int mid = left + (right - left) / 2;  int totalItems = 0;  // Calculate total items produced in 'mid' time  for (int i = 0; i < arr.length; i++) {  totalItems += mid / arr[i];  }  // If we can produce at least m items  // update answer  if (totalItems >= m) {  ans = mid;    // Search for smaller time  right = mid - 1;  }   else {    // Search in right half  left = mid + 1;  }  }    return ans;  }  public static void main(String[] args) {    int[] arr = {2 4 5};  int m = 7;  System.out.println(minTimeReq(arr m));  } } 
Python
# Python program to find minimum time  # required to produce m items using  # Binary Search Approach def minTimeReq(arr m): # Find the minimum value in arr manually minMachineTime = arr[0] for i in range(1 len(arr)): if arr[i] < minMachineTime: minMachineTime = arr[i] # Define the search space left = 1 right = m * minMachineTime ans = right while left <= right: # Calculate mid time mid = left + (right - left) // 2 totalItems = 0 # Calculate total items produced in 'mid' time for i in range(len(arr)): totalItems += mid // arr[i] # If we can produce at least m items # update answer if totalItems >= m: ans = mid # Search for smaller time right = mid - 1 else: # Search in right half left = mid + 1 return ans if __name__ == '__main__': arr = [2 4 5] m = 7 print(minTimeReq(arr m)) 
C#
// C# program to find minimum time  // required to produce m items using  // Binary Search Approach using System; class GfG {    static int minTimeReq(int[] arr int m) {    // Find the minimum value in arr manually  int minMachineTime = arr[0];  for (int i = 1; i < arr.Length; i++) {  if (arr[i] < minMachineTime) {  minMachineTime = arr[i];  }  }  // Define the search space  int left = 1;  int right = m * minMachineTime;  int ans = right;    while (left <= right) {    // Calculate mid time  int mid = left + (right - left) / 2;  int totalItems = 0;  // Calculate total items produced in 'mid' time  for (int i = 0; i < arr.Length; i++) {  totalItems += mid / arr[i];  }  // If we can produce at least m items  // update answer  if (totalItems >= m) {  ans = mid;    // Search for smaller time  right = mid - 1;  }   else {    // Search in right half  left = mid + 1;  }  }    return ans;  }  static void Main() {    int[] arr = {2 4 5};  int m = 7;  Console.WriteLine(minTimeReq(arr m));  } } 
JavaScript
// JavaScript program to find minimum time  // required to produce m items using  // Binary Search Approach function minTimeReq(arr m) {    // Find the minimum value in arr manually  let minMachineTime = arr[0];  for (let i = 1; i < arr.length; i++) {  if (arr[i] < minMachineTime) {  minMachineTime = arr[i];  }  }  // Define the search space  let left = 1;  let right = m * minMachineTime;  let ans = right;    while (left <= right) {    // Calculate mid time  let mid = Math.floor(left + (right - left) / 2);  let totalItems = 0;  // Calculate total items produced in 'mid' time  for (let i = 0; i < arr.length; i++) {  totalItems += Math.floor(mid / arr[i]);  }  // If we can produce at least m items  // update answer  if (totalItems >= m) {  ans = mid;    // Search for smaller time  right = mid - 1;  }   else {    // Search in right half  left = mid + 1;  }  }    return ans; } // Driver code let arr = [2 4 5]; let m = 7; console.log(minTimeReq(arr m)); 

الإخراج
8 

تعقيد الوقت: O(n log(m*min(arr))) نظرًا لأن البحث الثنائي يقوم بتشغيل السجل (m × min(arr)) مرات في كل فحص لعدد n من الأجهزة.
تعقيد الفضاء: O(1) حيث يتم استخدام عدد قليل فقط من المتغيرات الإضافية مما يجعلها مساحة ثابتة.
 

إنشاء اختبار