--- author: nguyencter tags: Buildcol title: Buildcol Solution --- $\Huge\text{Buildcol Solution}$ ------- :::info 🔗 Links: [Đề bài](https://drive.google.com/file/d/1sYMm7d5eVkm-T678yj2KK759Jz-mBUJO/view?usp=sharing) 📌 Tags: `binary search` ✍️ Writer: nguyencter 📋 Content: [TOC] ::: ----- ## Giới Thiệu Đề Bài Một con mương cung cấp nước cho đồng ruộng. Để điều tiết dòng chảy, người dân đặt $n$ cột bê tông xếp cạnh nhau có cùng độ rộng với con mương. Dãy $a$ gồm $n$ số là độ cao của $n$ cột bê tông Khi trời mưa, nước sẽ đọng lại ở các cột có độ cao thấp hơn. Để mặt đáy được bằng phẳng, mọi người muốn nâng các cột bê tông lên. Cụ thể, cần chọn một độ cao $X$ lớn nhất và nâng các cột có độ cao thấp hơn $X$ lên bằng $X$ mà vẫn đảm bảo lượng nước mưa được giữ lại ít nhất là $M$ đơn vị. **Yêu cầu:** Cho độ cao của $n$ cột bê tông và $M$ đơn vị nước cần giữ lại. Hãy tìm độ cao $X$ lớn nhất thoả mãn yêu cầu. Giả sử lượng nước khi trời mưa là đủ để ngập các vũng nước và nước không bị thất thoát. ----- ## Thuật toán Ta thấy nếu như nâng độ cao của bê tông lên $X$ mà vẫn thỏa mãn còn $M$ đơn vị nước thì với $k$ bất kì nhỏ hơn $X$ sẽ luôn thỏa mãn. Vì vậy ta có thể sử dụng phương pháp chặt nhị phân để tìm kết quả. Đầu tiên ta cần phải tìm xem lượng nước ban đầu đọng lại trên mỗi cột. Gọi $b[i]$ là lượng nước đọng lại trên cột $i$. Chặt nhị phân kết quả, với mỗi lần chặt kiểm tra xem tổng lượng nước đọng lại có ít hơn $M$ hay không. Độ phức tạp là $O(n*log(2*10^9)).$ ---- Tham khảo code mẫu ở [đây](https://github.com/nguyencter/CODE/blob/main/buildcol.cpp).