Tích lớn nhất ver 5
Đề bài
Cho mảng $A$ gồm $n$ số nguyên. Định nghĩa:
$f(l, r)$ $= (r - l + 1) \times \min(A[l], A[l+1], \ldots, A[r])$
Hãy tìm $f(l, r)$ lớn nhất với $1 \le l \le r \le n$.
Input:
- Dòng đầu tiên gồm số nguyên $n$ $(1 \le n \le 10^6)$.
- Dòng thứ hai gồm $n$ số nguyên $A[i]$ $(1 \le A[i] \le 10^9)$.
Output: in ra một số nguyên là giá trị $f(l, r)$ lớn nhất.
Subtask:
- $50\%$ số test đầu tiên có $n \le 10^4$;
- $30\%$ số test tiếp theo có $n \le 10^5$;
- $20\%$ số test còn lại không có giới hạn gì thêm.
3
1 2 34Giải thích ví dụ: chọn đoạn $[2, 3]$ gồm $2, 3$: độ dài $2$, nhỏ nhất là $2$ → $f = 4$. Các đoạn khác như $[1, 3]$ chỉ được $3 \times 1 = 3$, $[3, 3]$ được $1 \times 3 = 3$.
Lời mở đầu
Nếu vẽ mỗi số $A[i]$ thành một cột cao $A[i]$, rộng $1$ thì $f(l, r)$ chính là diện tích hình chữ nhật lớn nhất nằm gọn trong các cột từ $l$ đến $r$. Đây là bài kinh điển "hình chữ nhật lớn nhất trong biểu đồ cột", và cũng là bài mẫu hay nhất để học ngăn xếp đơn điệu: tìm phần tử nhỏ hơn gần nhất ở bên trái / bên phải của mọi phần tử chỉ trong $O(n)$. Mình sẽ đi từ cách duyệt mọi đoạn (ăn subtask 1) tới cách dùng ngăn xếp (full điểm), kèm kết quả chạy thật trên bộ test của CLUE.
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 OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ 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ì?
| Test | n | A[i] | Có giá trị lặp | Đáp án |
|---|---|---|---|---|
| 1 – 20 | 3 … 10 | 1 … 20 | 12/20 | 4 … 70 |
| 21 – 50 | 10.000 | 1 … 999.996.003 | 30/30 | 1.806.776.536 … 3.489.741.588 |
| 51 – 80 | 100.000 | 1 … 999.993.810 | 30/30 | 2.248.941.774 … 3.213.598.328 |
| 81 – 100 | 1.000.000 | 1 … 999.999.594 | 20/20 | 2.678.536.744 … 3.712.201.030 |
- Bộ test có 100 test, khớp đúng 3 subtask của đề: test 1–50 có $n \le 10^4$ (20 test đầu chỉ có $n \le 10$, 30 test sau có $n = 10^4$), test 51–80 có $n = 10^5$, test 81–100 có $n = 10^6$.
- Từ test 21 trở đi các số $A[i]$ trải đều tới gần $10^9$ và có nhiều giá trị lặp. Đáp án của 65 test vượt quá $2^{31} - 1$ nên bắt buộc dùng
long longcho kết quả (tích $(r - l + 1) \cdot \min$ có thể tới $10^6 \cdot 10^9 = 10^{15}$).
Các subtask khớp với bộ test như sau (ô ghi số test đúng của từng cách – chạy thật):
| Subtask | Điều kiện | Các test | Cách 1 C++ | Cách 2 C++ | Cách 1 Python | Cách 2 Python |
|---|---|---|---|---|---|---|
| 1 (50%) | $n \le 10^4$ | 1 – 50 | 50/50 | 50/50 | 20/50 | 50/50 |
| 2 (30%) | $n \le 10^5$ | 51 – 80 | 0/30 | 30/30 | 0/30 | 30/30 |
| 3 (20%) | $n \le 10^6$ | 81 – 100 | 0/20 | 20/20 | 0/20 | 0/20 |
Ý tưởngĐoán trước phần tử nhỏ nhất
Đoạn tối ưu $[l, r]$ nào cũng có một phần tử nhỏ nhất, giả sử là $A[i]$. Đảo góc nhìn: với mỗi $i$, giả sử $A[i]$ là phần tử nhỏ nhất của đoạn, đoạn nên dài bao nhiêu?
- Đoạn phải chứa $i$ và mọi phần tử trong đoạn phải $\ge A[i]$.
- Muốn tích lớn thì đoạn càng dài càng tốt → kéo dài sang trái và sang phải tới khi gặp phần tử nhỏ hơn $A[i]$ thì dừng.
$\text{đáp án}$ $= \max_{i} \big(R[i] - L[i] - 1\big) \times A[i]$
Vì đoạn tối ưu luôn được "đếm" ở đúng phần tử nhỏ nhất của nó nên lấy max theo mọi $i$ là ra đáp án. Em nhập dãy rồi bấm Tiếp để xem từng cột "lan" sang hai bên (cột vàng là $A[i]$ đang xét, khung đỏ là hình chữ nhật của nó, khung xanh nét đứt là tốt nhất hiện tại):
Việc còn lại là tính $L[i], R[i]$ thật nhanh. Lan từng bước như widget thì tệ nhất vẫn là $O(n^2)$ (ví dụ dãy toàn số bằng nhau). Ngăn xếp đơn điệu ở Cách 2 sẽ làm việc này trong $O(n)$.
Cách 1Duyệt mọi đoạn – O(n²)
Cố định đầu trái $l$, cho $r$ chạy từ $l$ tới $n$. Mỗi lần thêm $A[r]$ vào đoạn thì min mới là min(mn, a[r]) – không phải tính lại cả đoạn. Như vậy mỗi đoạn chỉ tốn $O(1)$.
- Biến
mngiữ min của đoạn $[l, r]$, được cập nhật dần khi $r$ tăng. a[],mn,ansđều làlong longđể tích(r - l + 1) * mnđược tính bằnglong long, không bị tràn.- Có $\frac{n(n+1)}{2}$ đoạn: với $n = 10^4$ là $5 \cdot 10^7$ đoạn – chạy tốt; với $n = 10^5$ là $5 \cdot 10^9$ – quá thời gian.
Kết quả chạy thật: bản C++ đúng 50/100 test (quá 1 giây ở các test 51–100), test đúng chạy lâu nhất 0.071s; bản Python đúng 20/100 test (quá thời gian ở các test 21–100), lâu nhất 0.02s.
Cách 2Ngăn xếp đơn điệu – O(n)
Tính $L[i]$ bằng cách duyệt $i$ từ trái sang phải và giữ một ngăn xếp chứa các chỉ số mà giá trị tăng dần từ đáy lên đỉnh:
- Khi xét $A[i]$: các phần tử ở đỉnh có giá trị $\ge A[i]$ thì bỏ ra (pop). Chúng không bao giờ là "phần tử nhỏ hơn gần nhất" của ai ở sau nữa, vì $A[i]$ vừa ở gần hơn vừa nhỏ hơn hoặc bằng.
- Sau khi pop, đỉnh ngăn xếp (nếu còn) chính là vị trí gần nhất bên trái có giá trị $< A[i]$ → đó là $L[i]$; ngăn xếp rỗng thì $L[i] = 0$.
- Đẩy $i$ vào ngăn xếp.
$R[i]$ làm y hệt nhưng duyệt từ phải sang trái. Mỗi chỉ số được push đúng 1 lần và pop tối đa 1 lần nên mỗi lượt duyệt chỉ tốn $O(n)$ dù có vòng while bên trong.
- Điều kiện pop là
>=ở cả hai lượt: các phần tử bằng $A[i]$ cũng bị bỏ, nhờ vậy đoạn của $A[i]$ được kéo dài qua các phần tử bằng nó (vẫn đúng vì min của đoạn vẫn là $A[i]$). - Nhớ dọn rỗng ngăn xếp (
while(!st.empty()) st.pop();) trước lượt thứ hai. 1LL * (R[i] - L[i] - 1) * a[i]: nhân với1LLtrước để phép nhân thực hiện trênlong long, tránh tràn sốint.- Mảng $10^6$ phần tử nên khai báo toàn cục; đọc nhanh bằng
ios::sync_with_stdio(0); cin.tie(0);.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.136s; bản Python đúng 80/100 test (quá thời gian ở các test 81–100), lâu nhất 0.17s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất (test đúng) | Ghi chú |
|---|---|---|---|---|
| 1. Duyệt mọi đoạn | C++ | 50/100 | 0.071s | Quá thời gian ở test 51–100 |
| Python | 20/100 | 0.024s | Quá thời gian ở test 21–100 | |
| 2. Ngăn xếp đơn điệu | C++ | 100/100 | 0.136s | Full điểm |
| Python | 80/100 | 0.170s | Quá thời gian ở test 81–100 |
Nhận xét
Đăng nhận xét