寻找完成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