Lời giải: Robot cắt cỏ

Ý tưởng

Với thời gian \(T\) cho mỗi máy, bãi cỏ \(i\) cần \(\lceil t_i / T \rceil\) lượt máy-slot để hoàn thành (vì bãi có thể chia nhỏ cho nhiều máy cùng cắt). Tổng số slot cho mọi bãi là:

\[ S(T) = \sum_{i=1}^{N} \left\lceil \frac{t_i}{T} \right\rceil \]

Để có thể hoàn thành mọi bãi, tổng slot cần \(\le K\) (số máy có sẵn). \(S(T)\) là hàm đơn điệu giảm theo \(T\). Ta tìm \(T\) nhỏ nhất với \(S(T) \le K\).

Thuật toán

• Cận dưới: \(1\).
• Cận trên: \(\max t_i\) (lúc đó mỗi bãi cần \(\lceil t_i / T \rceil = 1\) slot, tổng \(= N \le K\)).
• Với \(mid\): tính tổng ceiling; nếu \(\le K\) thì \(hi = mid\). Ngược lại \(lo = mid + 1\).

Độ phức tạp

• Thời gian: \(O(N \log(\max t_i))\).
• Bộ nhớ: \(O(N)\).

Cạm bẫy

• Vì \(K \ge N\) ràng buộc của bài toán, luôn có nghiệm.
• Dùng long long cho tổng vì tổng có thể rất lớn.

Mã nguồn tham khảo

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

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