이 문제에서는 n개의 요소와 정수 h로 구성된 배열 arr[]가 제공됩니다. 배열 arr[]의 각 요소에는 해당 사람의 보류 중인 작업 수가 포함되고 H는 작업을 완료하는 데 남은 시간(시간)입니다. 우리의 임무는 모든 작업을 완료할 수 있는 최소 속도를 찾는 것입니다.
문제 설명 :H 시간 안에 배열에 주어진 모든 작업을 완료하려면 한 사람이 한 시간에 완료해야 하는 작업의 수를 찾아야 합니다. 그가 1시간 이내에 arr[i]에 지정된 모든 것을 완료할 수 있다면 우리는 나머지 시간 동안 이상적으로 앉아서 시간이 끝나면 다음 작업 세트로 이동할 것입니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
arr[] = {4, 5, 1, 7, 8}, H = 5 출력
8
설명
그 사람은 5시간 동안 5세트의 작업을 완료해야 합니다. 따라서 1시간 동안의 최대 작업 수로 세트를 수행해야 하며, 이는 자신의 속도가 됩니다.
솔루션 접근 방식
문제를 해결하려면 그가 모든 작업을 수행할 수 있는 최소 속도를 찾아야 합니다. 그래서 그 사람이 모든 일을 할 수 있는 첫 번째 가치가 주어진 시간이라는 것을 알게 될 것입니다.
1에서 최대 0까지의 범위 내에서 속도를 검색합니다. 한 번에 할 수 있는 작업. 이 값이 클 수 있으므로 계산을 쉽게 하기 위해 이진 검색을 사용합니다.
현재 속도 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