Xây chuồng cao tầng

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

1. 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.

2. 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}$.

3. 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 $\ge x$.

Thuật toán

1. 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))\ge x$, tức là lợi ích biên của bò thứ $c_i$ vẫn $\ge x$.
   • Giải bất phương trình: $c_i(c_i+1)\le a_i/x$, suy ra $c_i=\lfloor (\sqrt{1+4a_i/x}-1)/2\rfloor$.
   • Tổng $\sum c_i$ cho biết số bò cần dùng. Nếu $\sum c_i\ge K$ thì tăng $x$, ngược lại giảm $x$.

2. 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$.

3. 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(200N)\approx O(N)$.
• Bộ nhớ: $O(N)$