Dané n stroje reprezentované celočíselným poľom arr[] kde arr[i] označuje čas (v sekundách), ktorý zaberá i-tý stroj na výrobu jeden položka. Všetky stroje fungujú súčasne a nepretržite. Okrem toho dostaneme aj celé číslo m predstavujúci celkový počet požadované položky . Úlohou je určiť minimálny čas potrebné presne vyrobiť m položky efektívne.
Príklady:
Vstup: arr[] = [2 4 5] m = 7
výstup: 8
Vysvetlenie: Optimálny spôsob výroby 7 položky v minimálne čas je 8 sekúnd. Každý stroj vyrába položky rôznymi rýchlosťami:
- Stroj 1 produkuje položku každý 2 sekúnd → Produkuje 8/2 = 4 položky v 8 sekúnd.
- Stroj 2 produkuje položku každý 4 sekúnd → Produkuje 8/4 = 2 položky v 8 sekúnd.
- Stroj 3 produkuje položku každý 5 sekúnd → Produkuje 8/5 = 1 položka v 8 sekúnd.
Celkový počet vyrobených položiek v 8 sekundy = 4 + 2 + 1 = 7
Vstup: arr[] = [2 3 5 7] m = 10
výstup: 9
Vysvetlenie: Optimálny spôsob výroby 10 položky v minimálne čas je 9 sekúnd. Každý stroj vyrába položky rôznymi rýchlosťami:
- Stroj 1 vyrobí každý kus 2 sekundy - Produkuje 9/2 = 4 položky za 9 sekúnd.
- Stroj 2 vyrobí každý kus 3 sekundy - Produkuje 9/3 = 3 položky za 9 sekúnd.
- Stroj 3 vyrobí každý kus 5 sekundy - Produkuje 9/5 = 1 položka za 9 sekúnd.
- Stroj 4 vyrobí každý kus 7 sekundy - Produkuje 9/7 = 1 položka za 9 sekúnd.
Celkový počet vyrobených položiek v 9 sekundy = 4 + 3 + 1 + 1 = 10
Obsah
- Použitie metódy hrubej sily - O(n*m*min(arr)) Čas a O(1) Priestor
- Použitie binárneho vyhľadávania - O(n*log(m*min(arr))) Čas a O(1) Priestor
Použitie metódy hrubej sily - O(n*m*min(arr)) Čas a O(1) Priestor
C++Myšlienka je postupne kontrolovať minimálny čas potrebný na presnú výrobu m položky. Začíname s čas = 1 a neustále ho zvyšujte až do celkového počtu položiek vyrobených všetkými strojmi ≥ m . V každom časovom kroku vypočítame počet položiek, ktoré môže každý stroj vyrobiť čas / arr[i] a zhrnúť ich. Pretože všetky stroje fungujú súčasne tento prístup zabezpečuje, že nájdeme najmenší platný čas.
// 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));
Výstup
8
Časová zložitosť: O(n*m*min(arr)) pretože pre každú časovú jednotku (až do m * min(arr)) iterujeme cez n strojov, aby sme spočítali vyrobené položky.
Priestorová zložitosť: O(1) pretože sa používa len niekoľko celočíselných premenných; nie je pridelené žiadne miesto navyše.
Použitie binárneho vyhľadávania - O(n*log(m*min(arr))) Čas a O(1) Priestor
The nápad je použiť Binárne vyhľadávanie namiesto kontroly zakaždým postupne pozorujeme, že celkový počet položiek vyrobených v danom čase T dá sa započítať O(n) . Kľúčovým postrehom je, že minimálny možný čas je 1 a maximálny možný čas je m * minMachineTime . Prihláškou binárne vyhľadávanie v tomto rozsahu opakovane kontrolujeme strednú hodnotu, aby sme zistili, či je dostatočná, a podľa toho upravíme priestor vyhľadávania.
Kroky na implementáciu vyššie uvedenej myšlienky:
- Nastavte doľava do 1 a správne do m * minMachineTime na definovanie vyhľadávacieho priestoru.
- Inicializovať ans s správne na uloženie minimálneho potrebného času.
- Spustite binárne vyhľadávanie zatiaľ čo vľavo je menšie alebo rovné správne .
- Vypočítajte stred a vypočítajte totalItems iterovaním cez arr a zhrnutie stred / arr[i] .
- Ak je totalItems aspoň m aktualizovať rokov a hľadať kratší čas. V opačnom prípade upravte vľavo do stred + 1 na dlhší čas.
- Pokračujte v hľadaní kým sa nenájde optimálny minimálny čas.
// 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));
Výstup
8
Časová zložitosť: O(n log(m*min(arr))) ako Binary Search spustí log(m × min(arr)) krát pri každej kontrole n počítačov.
Priestorová zložitosť: O(1) pretože sa používa iba niekoľko premenných navyše, čo z neho robí konštantný priestor.