Annettu n koneet, joita edustaa kokonaislukutaulukko arr[] jossa arr[i] tarkoittaa aikaa (sekunteina), jonka i-th kone tuottaa yksi kohde. Kaikki koneet toimivat samanaikaisesti ja jatkuvasti. Lisäksi meille annetaan myös kokonaisluku m edustaa kokonaismäärää tarvittavat tavarat . Tehtävänä on määrittää minimiaika tarvitaan tuottamaan tarkasti m kohteita tehokkaasti.
Esimerkkejä:
Syöte: arr[] = [2 4 5] m = 7
Lähtö: 8
Selitys: Optimaalinen tapa tuottaa 7 kohteita minimi aika on 8 sekuntia. Jokainen kone tuottaa tuotteita eri hinnoilla:
- Kone 1 tuottaa tuotteen joka 2 sekuntia → Tuottaa 8/2 = 4 kohteita sisään 8 sekuntia.
- Kone 2 tuottaa tuotteen joka 4 sekuntia → Tuottaa 8/4 = 2 kohteita sisään 8 sekuntia.
- Kone 3 tuottaa tuotteen joka 5 sekuntia → Tuottaa 8/5 = 1 kohde sisään 8 sekuntia.
Tuotteita yhteensä vuonna 8 sekuntia = 4 + 2 + 1 = 7
Syöte: arr[] = [2 3 5 7] m = 10
Lähtö: 9
Selitys: 10 kohteita minimi aika on 9 sekuntia. Jokainen kone tuottaa tuotteita eri hinnoilla:
- Kone 1 tuottaa tuotteen joka kerta 2 sekuntia - tuottaa 9/2 = 4 kohteita 9 sekunnissa.
- Kone 2 tuottaa jokaisen tuotteen 3 sekuntia - tuottaa 9/3 = 3 kohteita 9 sekunnissa.
- Kone 3 tuottaa jokaisen tuotteen 5 sekuntia - tuottaa 9/5 = 1 kohde 9 sekunnissa.
- Kone 4 tuottaa jokaisen tuotteen 7 sekuntia - tuottaa 9/7 = 1 kohde 9 sekunnissa.
Vuonna tuotetut tuotteet yhteensä 9 sekuntia = 4 + 3 + 1 + 1 = 10
Sisällysluettelo
- Brute Force -menetelmän käyttäminen - O(n*m*min(arr)) aika ja O(1) avaruus
- Binaarihaun käyttäminen - O(n*log(m*min(arr))) Aika ja O(1)-avaruus
Brute Force -menetelmän käyttäminen - O(n*m*min(arr)) aika ja O(1) avaruus
C++Ideana on asteittain tarkistaa tarkalleen tuottamiseen tarvittava vähimmäisaika m kohteita. Aloitamme kanssa aika = 1 ja nosta sitä, kunnes kaikkien koneiden tuottamat tuotteet ovat yhteensä ≥ m . Kussakin aikavaiheessa laskemme tuotteiden määrän, jonka kukin kone voi käyttää aika / arr[i] ja tiivistää ne. Koska kaikki koneet toimivat samanaikaisesti Tämä lähestymistapa varmistaa, että löydämme pienimmän voimassa olevan ajan.
// 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));
Lähtö
8
Aika monimutkaisuus: O(n*m*min(arr)) koska kullekin aikayksikölle (jopa m * min(arr)) iteroimme n koneen läpi laskeaksemme tuotetut tuotteet.
Tilan monimutkaisuus: O(1) koska vain muutamia kokonaislukumuuttujia käytetään; ylimääräistä tilaa ei ole varattu.
Binaarihaun käyttäminen - O(n*log(m*min(arr))) Aika ja O(1)-avaruus
The idea on käyttää Binäärihaku sen sijaan, että tarkistaisit joka kerta peräkkäin havaitsemme, että tiettynä aikana tuotettujen tuotteiden kokonaismäärä T voidaan laskea sisään O(n) . Keskeinen huomio on, että pienin mahdollinen aika on 1 ja suurin mahdollinen aika on m * minMachineTime . Hakemalla binäärihaku tällä alueella tarkistamme toistuvasti keskiarvon määrittääksemme, onko se riittävä, ja säädämme hakutilaa vastaavasti.
Toimenpiteet yllä olevan idean toteuttamiseksi:
- Aseta vasemmalle kohtaan 1 ja oikein to m * minMachineTime määrittääksesi hakutilan.
- Alusta ans kanssa oikein tallentaaksesi vaaditun vähimmäisajan.
- Suorita binäärihaku samalla kun vasemmalle on pienempi tai yhtä suuri kuin oikein .
- Laske mid ja laskea totalItems iteroimalla läpi arr ja yhteenveto mid / arr[i] .
- Jos totalItems on vähintään m päivittää vuotta ja etsi pienempää aikaa. Muuten säädä vasemmalle to keski + 1 pidemmäksi ajaksi.
- Jatka etsimistä kunnes optimaalinen vähimmäisaika löytyy.
// 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));
Lähtö
8
Aika monimutkaisuus: O(n log(m*min(arr))) koska binaarihaku suorittaa log(m × min(arr)) kertaa jokaisen n:n koneen tarkistuksen.
Tilan monimutkaisuus: O(1)