Lượng nước mưa giữ lại
Đề bài
Lượng Nước Mưa Giữ Lại
Cho $n$ $(n \le 10^6)$ các số nguyên $h[i]$ $(0 \le h[i] \le 10^9)$ biểu diễn bản đồ độ cao, trong đó chiều rộng của mỗi thanh là 1, hãy tính lượng nước mà các thanh có thể giữ lại sau khi mưa.
Dữ liệu vào: dòng đầu là $n$, dòng sau là $n$ số $h[1], h[2], \ldots, h[n]$.
Kết quả: một số nguyên là lượng nước giữ lại.
Hình vẽ minh hoạ ví dụ 1: màu đen là các cột, màu xanh là nước mưa được giữ lại (6 ô).
Ràng buộc:
- 30% số điểm đầu tiên có $h[i] \le 10^3$ và $n \le 10^2$.
- 30% số điểm tiếp theo có $h[i] \le 10^3$ và $n \le 10^4$.
- 40% điểm còn lại không có giới hạn gì thêm.
Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB.
12
0 1 0 2 1 0 1 3 2 1 2 166
4 2 0 3 2 59Lời mở đầu
Đây là bài "Trapping Rain Water" rất nổi tiếng, xuất hiện trong hầu hết các bộ đề phỏng vấn lẫn các khoá học cấu trúc dữ liệu. Có nhiều cách nhìn bài này: nhìn theo từng cột (mỗi cột chứa bao nhiêu nước) dẫn tới lời giải max tiền tố – hậu tố, còn nhìn theo từng lớp nằm ngang dẫn tới lời giải bằng ngăn xếp đơn điệu – đúng chủ đề của chương. Mình sẽ trình bày cả hai, kèm kết quả chạy thật trên bộ test.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test:
| Test | n | Độ cao $h_i$ | Đáp án |
|---|---|---|---|
| 1–20 | 5 … 12 | 0 … 20 | 0 … 54 |
| 21–30 | 100 | 0 … 1.000 | 51.406 … 61.015 |
| 31–60 | 10.000 | 0 … 1.000 | 5.882.465 … 6.023.758 |
| 61–80 | 100.000 | 0 … 1.000.000.000 | 69.542.461.836.922 … 70.119.508.878.082 |
| 81–100 | 1.000.000 | 0 … 1.000.000.000 | 698.293.695.275.454 … 700.052.719.415.156 |
- Subtask khớp đúng với bộ test: test 1–30 có $n \le 100$, $h \le 1000$; test 31–60 có $n = 10^4$, $h \le 1000$; test 61–100 có $n = 10^5$ (test 61–80) và $n = 10^6$ (test 81–100) với $h$ tới $10^9$.
- Đáp án lớn nhất cỡ $7 \cdot 10^{14}$ – vượt xa
int. Ngay cảmin(...) - h[i]cũng nên tính bằnglong longcho chắc, nên mình khai báo luôn mảng $h$ kiểulong long.
Số test đúng của từng cách theo subtask (chạy thật, giới hạn 1 giây):
| Subtask | Đề ghi | Test | Cách 1 $O(n^2)$ | Cách 2 (max 2 phía) | Cách 3 (ngăn xếp) |
|---|---|---|---|---|---|
| 1 (30%) | $h_i \le 10^3$, $n \le 10^2$ | 1–30 | 30/30 | 30/30 | 30/30 |
| 2 (30%) | $h_i \le 10^3$, $n \le 10^4$ | 31–60 | 30/30 | 30/30 | 30/30 |
| 3 (40%) | $n \le 10^6$, $h_i \le 10^9$ | 61–100 | 0/40 | 40/40 | 40/40 |
Ý tưởngNhìn theo cột và nhìn theo lớp
Ở ví dụ 2 ($4, 2, 0, 3, 2, 5$): cột thứ 3 (cao 0) có max trái 4, max phải 5 → nước lên tới 4, giữ $4 - 0 = 4$. Cộng lại $0 + 2 + 4 + 1 + 2 + 0 = 9$.
Em nhập dãy độ cao rồi bấm Tiếp để xem ngăn xếp "đổ nước" từng lớp. Cột vàng là cột $i$ đang xét, cột đỏ là đáy vừa lấy ra, cột xanh dương đậm là tường trái; lớp nước cam là lớp vừa đổ thêm:
Cách 1Mỗi cột tìm max hai phía – Subtask 1, 2
Làm thẳng theo công thức "nhìn theo cột": với mỗi cột $i$, chạy một vòng sang trái tìm trai, một vòng sang phải tìm phai.
- Cả hai vòng đều tính luôn chính cột $i$, nên
min(trai, phai) >= h[i]– không bao giờ cộng số âm. tonglàlong long; với subtask 1, 2 đáp án nhỏ nhưng subtask 3 cần tới $7 \cdot 10^{14}$.
Mỗi cột tốn $O(n)$ nên tổng $O(n^2)$: $n = 10^4$ là $10^8$ phép so sánh đơn giản – C++ vẫn kịp, nhưng $n = 10^5$ đã là $10^{10}$.
Kết quả chạy thật: Bản C++ đúng 60/100 test, quá thời gian ở test 61–100; test đúng chạy lâu nhất 0.08s. Bản Python đúng 30/60 test (mình chỉ chạy test 1–60), quá thời gian ở test 31–60; test đúng chạy lâu nhất 0.02s.
Gợi ý của đề "$h \le 10^3$" ở subtask 1, 2 còn cho phép một cách khác: xét từng mức nước $k = 1, 2, \ldots, \max h$ và đếm số ô ở độ cao $k$ nằm giữa hai cột cao $\ge k$ – độ phức tạp $O(n \cdot \max h)$, cũng chỉ ăn được 2 subtask đầu.
Cách 2Max tiền tố và max hậu tố – Full điểm
Hai vòng tìm max ở cách 1 lặp đi lặp lại rất nhiều. Ta tính trước một lần:
- $L[i] = \max(h_1, \ldots, h_i)$ $= \max(L[i-1], h_i)$ – max tiền tố, đi từ trái sang.
- $R[i] = \max(h_i, \ldots, h_n)$ $= \max(R[i+1], h_i)$ – max hậu tố, đi từ phải sang.
Khi đó $w_i = \min(L[i], R[i]) - h_i$, cộng lại trong $O(n)$.
Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.08s. Bản Python đúng 100/100 test; test đúng chạy lâu nhất 0.94s.
Cách 3Ngăn xếp đơn điệu – Full điểm
Đây là cài đặt của cách "nhìn theo lớp". Ngăn xếp lưu chỉ số cột (cần chỉ số để tính chiều rộng).
- Điều kiện
h[st.top()] < h[i]dùng dấu nhỏ hơn nghiêm ngặt: cột bằng nhau vẫn nằm lại trong ngăn xếp; khi sau này nó làm đáy với tường trái cao bằng nó thìcao = 0, cộng thêm 0 – không sai. - Nếu lấy đáy ra mà ngăn xếp rỗng thì không có tường trái: nước chảy ra ngoài bên trái,
break. Lúc này ngăn xếp đã rỗng nên vòngwhilecũng sẽ dừng. - Chiều rộng
i - t - 1chứ không phải 1: các cột giữa $t$ và đáy đã bị lấy ra trước đó, phía trên chúng đã có nước tới độ cao $h_{\text{đáy}}$, giờ ta đổ thêm một lớp phủ toàn bộ khoảng giữa hai tường. - Mỗi chỉ số vào ngăn xếp 1 lần, ra tối đa 1 lần → $O(n)$.
Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.11s. Bản Python đúng 100/100 test; test đúng chạy lâu nhất 0.92s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất | Ghi chú |
|---|---|---|---|---|
| 1. Mỗi cột tìm max 2 phía $O(n^2)$ | C++ | 60/100 | > 1s | quá thời gian test 61–100 |
| Python | 30/60 | > 1s | Mình chỉ chạy test 1–60; quá thời gian test 31–60 | |
| 2. Max tiền tố / hậu tố | C++ | 100/100 | 0.08s | full điểm |
| Python | 100/100 | 0.94s | full điểm | |
| 3. Ngăn xếp đơn điệu | C++ | 100/100 | 0.11s | full điểm |
| Python | 100/100 | 0.92s | full điểm |
sys.stdin.buffer) vẫn qua cả 100 test nhưng sát nút – khoảng 0.9 giây – nên nộp lên máy chấm có thể lúc qua lúc không; C++ thì dư sức.
Nhận xét
Đăng nhận xét