Hướng giải của Khỉ ăn chuối

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Lời giải: Khỉ ăn chuối

Ý tưởng

Với tốc độ \(X\) cố định, tổng số giờ cần dùng là:

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

Khi \(X\) tăng thì \(T(X)\) giảm hoặc giữ nguyên (đơn điệu). Vì vậy ta tìm \(X\) nhỏ nhất thỏa mãn \(T(X) \le H\).

Thuật toán

  • Cận dưới: \(1\) quả/giờ.
  • Cận trên: \(\max p_i\) (vì nếu \(X = \max p_i\), mỗi đống ăn trong \(1\) giờ, tổng cộng \(N \le H\) giờ — đủ).
  • Mỗi bước thử \(X = \lfloor (lo + hi)/2 \rfloor\):
    • Nếu tổng giờ \(\le H\): giảm \(hi = X\).
    • Ngược lại: tăng \(lo = X + 1\).

Độ phức tạp

  • Mỗi lần kiểm tra duyệt hết đống: \(O(N)\).
  • Tổng: \(O(N \log(\max p_i))\).

Mã nguồn tham khảo

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

bool check(const vector<long long>& pile, long long X, long long H) {
    long long hours = 0;
    for (long long p : pile) hours += (p + X - 1) / X;
    return hours <= H;
}

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

Nhận xét

Không có ý kiến tại thời điểm này.