資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告