Nguồn: Free Contest Trước tiên ta cần tìm số ~n~ lớn nhất sao cho cả ~k~ cửa sổ đều mở ~n~ tab mà không vượt quá bộ nhớ. Tổng bộ nhớ đã được sử dụng là: $$\displaystyle S = k(1 + 2 + 3 + ... + n) = k\frac{n(n + 1)}{2}$$ Dùng tìm kiếm nhị phân ta tìm được số ~n~, sau đó lấy phần dư còn lại của bộ nhớ và chia lấy nguyên cho ~n + 1~. Kết quả cuối cùng là: $$\displaystyle nk + \left\lfloor\frac{m - S}{n + 1}\right\rfloor$$ Độ phức tạp: ~O(Tlog(m))~.
Bình luận