好资源导航 » 文章资讯 » 寻找完成C ++中所有作业的最低速度

寻找完成C ++中所有作业的最低速度

2024-02-21 17:56:03 61

在这个问题中，我们得到了一个由n个元素和一个整数h组成的数组arr[]。数组arr[]的每个元素都包含该人的待处理作业数，H是完成作业所需的时间（以小时为单位）。我们的任务是找到完成所有作业的最低速度。

问题描述：我们需要找到一个人在一小时内需要完成的工作数量，以便在H小时内完成阵列中给出的所有工作。如果他能在不到一个小时的时间内完成所有在arr[i]上指定的任务，那么我们将在剩下的时间中处于理想状态，并在该小时结束后转到下一组工作。

让我们举个例子来了解这个问题，

输入

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

输出结果

解释

该人需要在5个小时内完成5组工作。因此，他/她需要在1小时内以最大的工作数量执行设置，这将是他/她的速度。

解决方法

为了解决该问题，我们需要找到他执行所有任务的最低速度。因此，我们将发现该人可以完成所有任务的第一个值是给定的时间量。

我们将在1到最大编号之间搜索速度。一口气完成的工作。由于该值可能很大，因此我们将使用二进制搜索来简化计算。

为了进行检查，如果以当前速度s可以解决问题，我们将找到完成一套所需的时间，然后将所有集合的时间相加。如果此时间小于H，则有可能不是。

该程序说明了我们解决方案的工作原理，

示例

#include 
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<<"及时完成所有作业的最低速度是 "<输出结果及时完成所有作业的最低速度是 4

寻找完成C ++中所有作业的最低速度

输入

解释

解决方法

示例

热门推荐

随机推荐