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

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

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

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

输入

arr[] = {4, 5, 1, 7, 8}, H = 5
输出结果
8

解释

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

解决方法

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

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

为了进行检查,如果以当前速度s可以解决问题,我们将找到完成一套所需的时间,然后将所有集合的时间相加。如果此时间小于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<<"及时完成所有作业的最低速度是 "<<calcJobMinSpeed(A, n, H);

   return 0;

}

输出结果
及时完成所有作业的最低速度是 4

以上是 寻找完成C ++中所有作业的最低速度 的全部内容, 来源链接: utcz.com/z/313890.html

回到顶部