与えられた n 整数配列で表されるマシン 到着[] どこ 到着しました は、実行にかかった時間 (秒単位) を示します。 i番目 生産する機械 1つ アイテム。すべての機械が動作します 同時に そして継続的に。さらに、整数も与えられます メートル の合計数を表します 必要なアイテム 。タスクは、 最低時間 正確に生産するために必要な メートル アイテムを効率よく。
例:
入力： 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 はアイテムを 1 つずつ生産します 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) 空間
の アイデア 使うことです 二分探索 毎回チェックするのではなく 順次 指定された時間内に生産されたアイテムの合計が観察されます。 T で計算できます の上） 。重要な観察事項は、可能な最小時間は次のとおりであるということです。 1 そして可能な最大時間は m * 分マシン時間 。申請することで 二分探索 この範囲では、中間値を繰り返しチェックして十分かどうかを判断し、それに応じて検索スペースを調整します。
上記のアイデアを実装する手順は次のとおりです。
- 左にセット 1に、そして 右 に m * 分マシン時間 検索スペースを定義します。
- ansを初期化する と 右 必要最小限の時間を保存します。
- 二分探索を実行する その間 左 以下である 右 。
- 中間を計算する そして 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) 追加の変数がいくつかだけ使用されるため、定数スペースになります。