Trong bài toán này, chúng ta đưa ra một mảng arr [] gồm n phần tử và aninteger h. Mỗi phần tử của mảng arr [] chứa số lượng công việc đang chờ xử lý của người đó và H là thời gian còn lại để hoàn thành công việc (tính bằng Giờ). Nhiệm vụ của chúng tôi là Tìm tốc độ tối thiểu để hoàn thành tất cả Công việc.
Mô tả sự cố :Ta cần tìm số công việc người đó cần hoàn thành trong một giờ để có thể hoàn thành tất cả các công việc đã cho trong mảng trong H giờ. Nếu anh ấy có thể hoàn thành tất cả những gì được chỉ định tại arr [i] trong vòng chưa đầy một giờ, chúng tôi sẽ ngồi một cách lý tưởng trong khoảng thời gian còn lại và sau khi kết thúc giờ, hãy chuyển sang nhóm công việc tiếp theo.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {4, 5, 1, 7, 8}, H = 5 Đầu ra
8
Giải thích
Người đó cần hoàn thành 5 bộ công việc trong 5 giờ. Vì vậy, anh ấy / cô ấy cần thực hiện tốt nhóm với số lượng công việc tối đa trong 1 giờ sẽ là tốc độ của anh ấy / cô ấy.
Phương pháp tiếp cận giải pháp
Để giải quyết vấn đề, chúng ta cần tìm tốc độ tối thiểu mà anh ta có thể thực hiện tất cả các nhiệm vụ. Vì vậy, chúng tôi sẽ tìm giá trị đầu tiên mà một người có thể làm tất cả các nhiệm vụ là lượng thời gian đã cho.
Chúng tôi sẽ tìm kiếm tốc độ trong phạm vi từ 1 đến tối đa không. công việc phải làm tôi không cần phải làm. Vì giá trị này có thể lớn, chúng tôi sẽ sử dụng tìm kiếm nhị phân để dễ tính toán.
Để kiểm tra, nếu ở tốc độ hiện tại, người đó có thể giải quyết được vấn đề, chúng tôi sẽ tìm thời gian cần thiết để hoàn thành một bộ và sau đó cộng thời gian cho tất cả các bộ. Nếu thời gian này nhỏ hơn H, thì có thể là không.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
The minimum speed to finish all jobs in time is 4