주어진 N 정수 배열로 표현되는 기계 도착[] 어디 도착[i] 소요된 시간(초)을 나타냅니다. i번째 생산하는 기계 하나 목. 모든 기계가 작동합니다 동시에 그리고 지속적으로. 추가적으로 정수도 주어졌습니다. 중 총 개수를 나타내는 필수품 . 임무는 다음을 결정하는 것입니다. 최소 시간 정확하게 생산하기 위해 필요한 중 아이템을 효율적으로
예:
입력: arr[] = [2 4 5] m = 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
입력: arr[] = [2 3 5 7] m = 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) 공간
C++아이디어는 점진적으로 확인 정확하게 생산하는 데 필요한 최소 시간 중 항목. 우리는 다음과 같이 시작합니다 시간 = 1 모든 기계에서 생산되는 총 품목이 나올 때까지 계속 증가시킵니다. ≥m . 각 단계에서 우리는 다음을 사용하여 각 기계가 생산할 수 있는 품목 수를 계산합니다. 시간 / 도착[i] 그리고 그것들을 요약해 보세요. 모든 기계가 작동하기 때문에 동시에 이 접근 방식을 사용하면 가장 작은 유효 시간을 찾을 수 있습니다.
// 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));
산출
8
시간 복잡도: O(n*m*min(arr)) 각 시간 단위(최대 m * min(arr))에 대해 n개의 기계를 반복하여 생산된 품목 수를 계산하기 때문입니다.
공간 복잡도: O(1) 소수의 정수 변수만 사용되기 때문입니다. 추가 공간이 할당되지 않습니다.
이진 검색 사용 - O(n*log(m*min(arr))) 시간 및 O(1) 공간
그만큼 아이디어 사용하는 것입니다 이진 검색 매번 확인하는 것보다 순차적으로 우리는 주어진 시간에 생산된 총 품목이 티 에서 계산할 수 있습니다 에) . 중요한 관찰은 가능한 최소 시간이 다음과 같다는 것입니다. 1 가능한 최대 시간은 m * minMachineTime . 신청함으로써 이진 검색 이 범위에서 중간 값을 반복적으로 확인하여 그것이 충분한지 결정하고 이에 따라 검색 공간을 조정합니다.
위의 아이디어를 구현하는 단계:
- 왼쪽으로 설정 1에 그리고 오른쪽 에게 m * minMachineTime 검색 공간을 정의합니다.
- 초기화 ~와 함께 오른쪽 필요한 최소 시간을 저장합니다.
- 이진 검색 실행 ~하는 동안 왼쪽 다음보다 작거나 같음 오른쪽 .
- 중간 계산 totalItems 계산 반복함으로써 도착 그리고 요약하자면 중반 / 도착[i] .
- totalItems가 m 이상인 경우 업데이트 연령 그리고 더 작은 시간을 검색해 보세요. 그렇지 않으면 조정 왼쪽 에게 중간 + 1 더 오랜 시간 동안.
- 계속 검색 최적의 최소 시간을 찾을 때까지.
// 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));
산출
8
시간 복잡도: O(n log(m*min(arr))) 이진 검색은 n개의 머신을 검사할 때마다 log(m × min(arr))번 실행됩니다.
공간 복잡도: O(1) 몇 가지 추가 변수만 사용되어 일정한 공간을 만듭니다.