数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用C++查找完成所有工作的最低速度
在这个问题中，我们得到一个包含n个元素的数组arr[]和一个整数h。数组arr[]的每个元素包含该人员待处理的任务数量，而H是完成任务剩余的时间（以小时为单位）。我们的任务是找到完成所有工作的最低速度。
问题描述：我们需要找到一个人需要在一小时内完成的任务数量，以便在H小时内完成数组中给出的所有任务。如果他可以在不到一小时内完成所有指定的arr[i]，我们将理想地等待剩余时间，并在小时结束之后，转到下一组任务。
让我们举个例子来理解这个问题：
输入
arr[] = {4, 5, 1, 7, 8}, H = 5输出
8
解释
这个人需要在5小时内完成5组任务。因此，他/她需要在一小时内完成任务数量最多的那一组，这将是他的/她的速度。
解决方案方法
为了解决这个问题，我们需要找到他可以完成所有任务的最低速度。因此，我们将找到第一个值，在这个值下，该人员可以在给定的时间内完成所有任务。
我们将在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<<"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
更新于：2021年3月12日
140 次浏览
广告