C++ですべてのジョブを完了するための最低速度を見つける

この問題では、n個の要素と整数hで構成される配列arr[]が与えられます。配列arr[]の各要素には、その人の保留中のジョブの数が含まれ、Hはジョブを完了するための残り時間（時間単位）です。私たちの仕事は、すべてのジョブを完了するための最低速度を見つけることです。

問題の説明 ：配列で指定されたすべてのジョブをH時間で完了するには、その人が1時間に完了する必要のあるジョブの数を見つける必要があります。彼がarr[i]で指定されたすべてを1時間以内に完了することができれば、残りの時間は理想的に座って、1時間の終わりの後、次の一連の仕事に移ります。

問題を理解するために例を見てみましょう

入力

arr[] = {4, 5, 1, 7, 8}, H = 5

出力

8

説明

その人は5時間で5セットの仕事を完了する必要があります。したがって、彼/彼女は、彼/彼女の速度となる1時間の最大ジョブ数でセットを実行する必要があります。

ソリューションアプローチ

この問題を解決するには、彼がすべてのタスクを実行できる最低速度を見つける必要があります。したがって、その人がすべてのタスクを実行できる最初の値は、指定された時間です。

1から最大数の範囲内の速度を検索します。一度に行う仕事の。この値は大きくなる可能性があるため、計算を容易にするために二分探索を使用します。

確認するために、現在の速度sで人が問題を解決できるかどうかを確認するために、1つのセットを完了するのにかかる時間を見つけて、すべてのセットの時間を追加します。この時間がH未満の場合、それ以外の場合は可能です。

ソリューションの動作を説明するプログラム

例

#include <bits/stdc++.h>
using namespace std;
bool canDoJobInTime(int A[], int n, int H, int speed) {
   int timeTaken = 0;
   for (int i = 0; i < n; ++i)
      timeTaken += (A[i] - 1) / speed + 1;
   return timeTaken <= H;
}
int calcJobMinSpeed(int A[], int n, int H) {
   if (H < n)
      return -1;
   int maxJob = A[0];
   for(int i = 1; i < n; i++)
      maxJob = max(A[i], maxJob);
   int start = 1, end = maxJob;
   while (start < end) {
      int mi = start + (end - start) / 2;
      if (!canDoJobInTime(A, n, H, mi))
         start = mi + 1;
      else
         end = mi;
   }
   return start;
}
int main() {
   int A[] = { 3, 6, 7, 11 }, H = 8;
   int n = sizeof(A) / sizeof(A[0]);
   cout<<"The minimum speed to finish all jobs in time is "<<calcJobMinSpeed(A, n, H);
   return 0;
}

出力

The minimum speed to finish all jobs in time is 4