Tìm tốc độ tối thiểu để hoàn thành tất cả công việc trong C++

Giới thiệu

Cho mảng arr[] n phần tử (số việc pending) và số giờ H. Mỗi giờ người làm được tối đa 'speed' việc. Nếu xong sớm thì nghỉ đến giờ sau. Tìm speed tối thiểu để hoàn thành trong H giờ.

Ví dụ minh họa

Đầu vào

arr[] = {4, 5, 1, 7, 8}, H = 5

Đầu ra

8

Giải thích

5 nhóm việc, 5 giờ ⇒ mỗi giờ làm 1 nhóm. Nhóm lớn nhất là 8 ⇒ speed = 8.

Phương pháp giải: Tìm kiếm nhị phân - O(N log M)

Speed nằm trong [1, max(arr)]. Dùng binary search tìm speed nhỏ nhất thỏa mãn. Hàm kiểm tra: tổng thời gian = Σ ceil(arr[i]/speed) ≤ H.

Chương trình minh họa

#include <bits/stdc++.h>
using namespace std;

bool canFinish(int A[], int n, int H, int speed) {
    int time = 0;
    for (int i = 0; i < n; ++i)
        time += (A[i] - 1) / speed + 1; // ceil(A[i]/speed)
    return time <= H;
}

int calcMinSpeed(int A[], int n, int H) {
    if (H < n) return -1;
    int maxJob = *max_element(A, A+n);
    int lo = 1, hi = maxJob;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (!canFinish(A, n, H, mid))
            lo = mid + 1;
        else
            hi = mid;
    }
    return lo;
}

int main() {
    int A[] = {3, 6, 7, 11}, H = 8;
    int n = sizeof(A)/sizeof(A[0]);
    cout << "Minimum speed to finish all jobs: " << calcMinSpeed(A, n, H);
    return 0;
}

Đầu ra

Minimum speed to finish all jobs: 4