Lời giải: Nhà máy K máy

Ý tưởng

Với thời gian thử \(T\), máy \(i\) hoàn thành \(\lfloor T / t_i \rfloor\) sản phẩm. Tổng số sản phẩm của cả nhà máy là:

\[ S(T) = \sum_{i=1}^{K} \left\lfloor \frac{T}{t_i} \right\rfloor \]

Đây là hàm đơn điệu tăng theo \(T\). Ta tìm \(T\) nhỏ nhất với \(S(T) \ge N\).

Thuật toán

• Cận dưới: \(1\).
• Cận trên: \(t_{\min} \cdot N\) (dùng máy nhanh nhất làm hết).
• Thử \(mid\): tính tổng sản phẩm. Nếu \(\ge N\): \(hi = mid\). Ngược lại: \(lo = mid + 1\).

Độ phức tạp

• Mỗi lần kiểm tra: \(O(K)\).
• Tổng: \(O(K \log(t_{\min} \cdot N))\).

Cạm bẫy

• Cận trên \(t_{\min} \cdot N\) có thể rất lớn (\(\le 10^{14}\)). Dùng long long.

Mã nguồn tham khảo

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long N, K;
    cin >> N >> K;
    vector<long long> t(K);
    long long mn = LLONG_MAX;
    for (int i = 0; i < K; i++) {
        cin >> t[i];
        mn = min(mn, t[i]);
    }
    long long lo = 1, hi = mn * N;
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        long long total = 0;
        for (long long ti : t) {
            total += mid / ti;
            if (total >= N) break;
        }
        if (total >= N) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << "\n";
    return 0;
}