Hướng dẫn giải của Xây chuồng cao tầng

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Xây chuồng cao tầng

Hướng tiếp cận

Bài toán yêu cầu phân bổ $K$ con bò vào $N$ tầng (mỗi tầng ít nhất 1 bò) sao cho tổng $\sum a_{i} / c_{i}$ nhỏ nhất. Đây là bài toán tối ưu phân bổ tài nguyên với hàm lợi ích giảm dần.

Nhận xét quan trọng

Lợi ích biên giảm dần: Khi thêm bò thứ $(c + 1)$ vào tầng $i$ , lợi ích (giảm thời gian) là $a_{i} / c - a_{i} / (c + 1) = a_{i} / (c (c + 1))$ . Giá trị này giảm dần khi $c$ tăng.
Tham lam thông thường quá chậm: Cách tham lam "luôn thêm bò vào tầng có lợi ích biên lớn nhất" đúng nhưng có độ phức tạp $O (K \log N)$ , quá chậm khi $K$ lên đến $10^{12}$ .
Tìm kiếm nhị phân trên lợi ích biên: Thay vì thêm từng bò, ta tìm kiếm nhị phân trên giá trị $x$ - lợi ích biên nhỏ nhất mà ta chấp nhận khi thêm bò. Với mỗi giá trị $x$ , ta tính được số bò tối đa có thể phân bổ sao cho mọi bò đều có lợi ích biên $\geq x$ .

Thuật toán

Tìm kiếm nhị phân trên giá trị thực $x$ (lợi ích biên ngưỡng):
- Với mỗi tầng $i$ , tìm số bò $c_{i}$ lớn nhất sao cho $a_{i} / (c_{i} (c_{i} + 1)) \geq x$ , tức là lợi ích biên của bò thứ $c_{i}$ vẫn $\geq x$ .
- Giải bất phương trình: $c_{i} (c_{i} + 1) \leq a_{i} / x$ , suy ra $c_{i} = ⌊ (\sqrt{1 + 4 a_{i} / x} - 1) / 2 ⌋$ .
- Tổng $\sum c_{i}$ cho biết số bò cần dùng. Nếu $\sum c_{i} \geq K$ thì tăng $x$ , ngược lại giảm $x$ .
Xử lý sau tìm kiếm nhị phân:
- Sau khi hội tụ, ta có ngưỡng $x$ và phân bổ ban đầu $c_{i}$ cho mỗi tầng.
- Nếu tổng $\sum c_{i} < K$ , ta có dư bò. Các bò dư được thêm vào các tầng có lợi ích biên đúng bằng $x$ (tức $a_{i} / (c_{i} (c_{i} + 1)) = x$ ).
- Nếu tổng $\sum c_{i} > K$ , ta bớt bò ở các tầng có lợi ích biên bằng $x$ .
Tính kết quả: Tổng $\sum a_{i} / c_{i}$ , làm tròn đến số nguyên gần nhất.

Độ phức tạp

Thời gian: $O (N \log V)$ với $V$ là khoảng tìm kiếm nhị phân (khoảng $200$ vòng lặp cho số thực), tức $O (200 N) \approx O (N)$ .
Bộ nhớ: $O (N)$

Bình luận

Không có bình luận tại thời điểm này.