Solutions of Leaky roof

Select solution language

kien10i Created at 1 likes

Nhận xét : với mỗi lần nhảy ta sẽ luôn tham lam chọn tấm ván xa nhất có thể nhảy được với mỗi vị trí ta sẽ tìm vị trí xa nhất mà nó có thể nhảy tới được khi dùng 1 tấm ván để tính điều này ta có thể sử dụng sweepline khi thoát ra duy trì 1 tập set khi thoát khỏi đoạn l-r cũng đồng nghĩa ta xoá r trong set đi => như vậy với mỗi vị trí ta đã xác định được vị trí xa nhất mà nó có thể tới khi dùng 1 tấm ván áp dụng sparetable để tính sau x tấm ván vị trí ta có thể che phủ là đến đâu => như vậy ta có thể chặt nhị phân để tìm ra đáp án tối ưu ĐPT O(nlog(n)^2)