Adott n egész számmal ábrázolt gépek arr[] ahol arr[i] azt az időt jelöli (másodpercben), amelyet a i-th gépet gyártani egy tétel. Minden gép működik egyidejűleg és folyamatosan. Ezenkívül egy egész számot is kapunk m teljes számát reprezentálva szükséges tételek . A feladat annak meghatározása minimális idő pontosan előállítani kell m elemeket hatékonyan.
Példák:
Bemenet: arr[] = [2 4 5] m = 7
Kimenet: 8
Magyarázat: A termelés optimális módja 7 tételek a minimális az idő az 8 másodpercig. Minden gép különböző ütemben állít elő termékeket:
- Gép 1 minden egyes terméket gyárt 2 másodperc → Előállít 8/2 = 4 tételek be 8 másodpercig.
- 2. gép minden egyes terméket gyárt 4 másodperc → Előállít 8/4 = 2 tételek be 8 másodpercig.
- 3. gép minden egyes terméket gyárt 5 másodperc → Előállít 8/5 = 1 tétel be 8 másodpercig.
A ben gyártott összes tétel 8 másodperc = 4 + 2 + 1 = 7
Bemenet: arr[] = [2 3 5 7] m = 10
Kimenet: 9
Magyarázat: A termelés optimális módja 10 tételek a minimális az idő az 9 másodpercig. Minden gép különböző ütemben állít elő termékeket:
- Az 1. gép minden alkalommal egy-egy elemet gyárt 2 másodperc – termel 9/2 = 4 elemeket 9 másodperc alatt.
- A 2. gép minden alkalommal egy-egy elemet gyárt 3 másodperc – termel 9/3 = 3 elemeket 9 másodperc alatt.
- A 3. gép minden alkalommal egy-egy elemet gyárt 5 másodperc – termel 9/5 = 1 elem 9 másodperc alatt.
- A 4-es gép minden alkalommal egy-egy elemet gyárt 7 másodperc – termel 9/7 = 1 elem 9 másodperc alatt.
A ben gyártott összes tétel 9 másodperc = 4 + 3 + 1 + 1 = 10
Tartalomjegyzék
- Brute Force Method használata – O(n*m*min(arr)) idő és O(1) tér
- Bináris keresés használata - O(n*log(m*min(arr))) Idő és O(1) tér
Brute Force Method használata – O(n*m*min(arr)) idő és O(1) tér
C++Az ötlet az, hogy fokozatosan ellenőrizni a pontos előállításhoz szükséges minimális idő m tételeket. Kezdjük azzal idő = 1 és folyamatosan növelje, amíg az összes gép által előállított tétel el nem éri ≥ m . Minden egyes időlépésben kiszámítjuk, hogy az egyes gépek hány darabot tudnak felhasználni idő / arr[i] és összegezze őket. Mivel minden gép működik egyidejűleg ez a megközelítés biztosítja, hogy megtaláljuk a legkisebb érvényes időt.
// C++ program to find minimum time // required to produce m items using // Brute Force Approach #include
// 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 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# 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 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));
Kimenet
8
Időbonyolultság: O(n*m*perc(arr)) mert minden időegységre (m * min(arr)) n gépen keresztül iterálunk az előállított cikkek megszámlálásához.
A tér összetettsége: O(1) mivel csak néhány egész változót használunk; nincs külön hely foglalva.
Bináris keresés használata - O(n*log(m*min(arr))) Idő és O(1) tér
A ötlet használni Bináris keresés ahelyett, hogy minden alkalommal ellenőrizné szekvenciálisan megfigyeljük, hogy az adott idő alatt előállított összes tétel T be lehet számolni On) . A legfontosabb megfigyelés az, hogy a lehetséges minimális idő az 1 és a lehetséges maximális idő az m * minGépidő . Jelentkezéssel bináris keresés ezen a tartományon többször ellenőrizzük a középértéket, hogy eldöntsük, elegendő-e, és ennek megfelelően módosítjuk a keresési teret.
A fenti ötlet megvalósításának lépései:
- Állítsa balra 1-hez és jobbra hogy m * minMachineTime a keresési tér meghatározásához.
- Ans inicializálása -vel jobbra a szükséges minimális idő tárolására.
- Futtassa a bináris keresést míg balra kisebb vagy egyenlő, mint jobbra .
- Számítsa ki a közepét és kiszámítja a totalItems keresztül iterálva arr és összegezve mid / arr[i] .
- Ha a totalItems legalább m frissítés évre és keressen rövidebb időt. Ellenkező esetben állítsa be balra hogy közepe + 1 nagyobb időre.
- Folytassa a keresést amíg meg nem találjuk az optimális minimális időt.
// C++ program to find minimum time // required to produce m items using // Binary Search Approach #include
// 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 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# 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 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));
Kimenet
8
Időbonyolultság: O(n log(m*min(arr))) mivel a bináris keresés lefuttatja a log(m × min(arr))-szor minden egyes n gép ellenőrzését.
A tér összetettsége: O(1) mivel csak néhány extra változót használnak, így állandó hely.