Hướng giải: Nhà máy

Nguồn: CSES

Ta thiết kế một hàm Check(x) để duyệt qua các máy và tính tổng số sản phẩm mà chúng có thể sản xuất trong ~x~ đơn vị thời gian. Hàm trả về true nếu số sản phẩm sản xuất được lớn hơn hoặc bằng số sản phẩm yêu cầu.

Ta có thể giải bài toán một cách hiệu quả bằng tìm kiếm nhị phân và gọi hàm trên. Ta tìm thời gian lớn nhất ~k~ sao cho không thể sản xuất đủ số lượng sản phẩm yêu cầu. Khi đó, ~k + 1~ chính là đáp án của bài toán.

Thuật toán có độ phức tạp ~O(n.log(M))~, trong đó ~M=10^{18}~ là đáp án lớn nhất có thể.