Đoạn con liên tiếp có tổng lớn nhất (độ dài từ L đến R)
Đề bài
Đoạn con liên tiếp có tổng lớn nhất (có số âm)
Cho dãy gồm $n$ số nguyên $a_1, a_2, \ldots, a_n$ và hai số nguyên dương $1 \le L \le R \le n$. Hãy tìm một dãy con gồm các phần tử liên tiếp có độ dài $s$ $(L \le s \le R)$ có tổng các phần tử là lớn nhất.
Input:
- Dòng đầu tiên gồm ba số nguyên $n, L, R$ $(1 \le n \le 10^5)$.
- Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ $(|a_i| \le 10^9)$.
Output: Gồm một dòng chứa một số là tổng các phần tử lớn nhất của dãy con tìm được thỏa mãn.
Subtask:
- Subtask 1 (30%): $n \le 100$;
- Subtask 2 (30%): $n \le 5000$;
- Subtask 3 (40%): Không có ràng buộc nào thêm.
Giải thích ví dụ: chọn đoạn $(3, -1, 5)$ ở vị trí 2..4, độ dài $3$ nằm trong $[2, 3]$, tổng bằng $7$. Đoạn $(1, 3, -1, 5)$ có tổng $8$ lớn hơn nhưng dài 4 > R nên không được chọn.
5 2 3
1 3 -1 5 -17Lời mở đầu
Bài "đoạn con có tổng lớn nhất" thì chắc các bạn gặp nhiều rồi, nhưng ở đây có thêm ràng buộc độ dài phải nằm trong $[L, R]$, nên mẹo Kadane quen thuộc không dùng thẳng được nữa. Mình sẽ đi từ cách vét cạn dễ hiểu nhất, rồi tối ưu dần: tổng cộng dồn, rồi tổng tiền tố + multiset để "trượt" một cửa sổ và luôn lấy được giá trị nhỏ nhất trong cửa sổ đó. Đây là kỹ thuật rất hay gặp trong chương Map/Set.
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ì?
Bộ test có 100 test, chia nhóm theo kích thước như sau:
| Test | n | Độ rộng R − L + 1 | $|a_i|$ lớn nhất | Số âm | Đáp án |
|---|---|---|---|---|---|
| 1–10 | 1 … 10 | ≤ 3 | 20 | 45% | -40 … 44 |
| 11–30 | 100 | ≤ 85 | 991.672.848 | 48% | -278.883.892 … 4.422.283.233 |
| 31–60 | 5.000 | ≤ 4.393 | 999.898.380 | 50% | -16.519.056.176 … 18.558.110.289 |
| 61–70 | 100.000 | ≤ 54.569 | 999.998.856 | 49% | 6.241.931.093 … 81.551.539.414 |
| 71–99 | 100.000 | ≤ 100.000 | 999.999.465 | 49% | 43.693.108.563 … 141.943.033.673 |
| 100 | 100.000 | ≤ 100.000 | 1.000.000.000 | 0% | 100.000.000.000.000 … 100.000.000.000.000 |
Đối chiếu subtask của đề với test thật (cả 3 subtask đều khớp với đề) và số test đúng của từng cách:
| Subtask | Đề ghi | Test | Cách 1 $O(n^3)$ | Cách 2 $O(n^2)$ | Cách 3 multiset |
|---|---|---|---|---|---|
| 1 (30%) | $n \le 100$ | 1–30 | 30/30 | 30/30 | 30/30 |
| 2 (30%) | $n \le 5000$ | 31–60 | 19/30 | 30/30 | 30/30 |
| 3 (40%) | $n \le 10^5$ | 61–100 | 2/40 | 5/40 | 40/40 |
- Đáp án âm: các test 3, 9–10, 24, 50, 55 có đáp án âm (ví dụ cả dãy đều âm). Nếu em khởi tạo
ans = 0thì sẽ in ra 0 – sai. Phải khởi tạoansthật nhỏ (LLONG_MIN). - Tràn số: test 100 có $10^5$ số đều bằng $10^9$, đáp án là $10^{14}$ – vượt xa
int. Tổng phải dùnglong long.
Ý tưởngTổng đoạn = hiệu hai tổng tiền tố
Gọi $p_i = a_1 + a_2 + \ldots + a_i$ (với $p_0 = 0$). Khi đó tổng đoạn $a_{i+1..j}$ (dài $j - i$) là $p_j - p_i$.
Cố định điểm cuối $j$. Độ dài $j - i$ phải nằm trong $[L, R]$, tức là $i$ chạy trong khoảng $[j - R,\ j - L]$ (và $i \ge 0$). Muốn $p_j - p_i$ lớn nhất thì phải chọn $p_i$ nhỏ nhất trong khoảng đó.
multiset (tự sắp xếp tăng dần, cho phép trùng nhau) thì phần tử nhỏ nhất luôn là *ms.begin(). Đáp án là max của $p_j - \min$.Vì sao là multiset mà không phải set? Vì các tổng tiền tố có thể trùng nhau: nếu dùng set thì 2 giá trị bằng nhau chỉ lưu 1 lần, đến lúc xoá một cái là mất luôn cái còn lại. Và khi xoá phải dùng ms.erase(ms.find(x)) để xoá đúng một bản sao – viết ms.erase(x) sẽ xoá hết mọi bản sao của $x$.
Em nhập dãy, $L$, $R$ rồi bấm Tiếp để xem cửa sổ trượt trên mảng tổng tiền tố:
Cách 1Vét cạn mọi đoạn – Subtask 1
Thử mọi điểm đầu $i$, mọi điểm cuối $j$ sao cho độ dài $j - i + 1 \in [L, R]$, rồi cộng lại các số từ $a_i$ đến $a_j$. Ba vòng lặp lồng nhau nên là $O(n^3)$ (đúng hơn là $O(n \cdot R^2)$).
- Vòng
jbắt đầu từi + L - 1(đoạn dài đúng $L$) và dừng ởmin(n, i + R - 1)(đoạn dài $R$, nhưng không được vượt quá $n$). anskhởi tạoLLONG_MINđể đúng cả khi mọi đoạn đều có tổng âm.
Kết quả chạy thật: bản C++ đúng 51/100 test (quá thời gian ở test 36, 38, 40, 43, 46–48, 52–54, 59, 61–65, 67, 69–100), test đúng chạy lâu nhất 0.96s; bản Python (chỉ chạy test 1–60) đúng 38/60 test (quá thời gian ở test 31–33, 36–38, 40–48, 51–54, 56, 58–59), test đúng lâu nhất 0.51s. Cách này ăn trọn subtask 1; ngoài ra những test có $R$ nhỏ (cả ở subtask 2 lẫn subtask 3) cũng qua, vì số phép tính thật ra cỡ $n \cdot R^2 / 2$ chứ không hẳn là $n^3$.
Cách 2Cộng dồn khi kéo dài đoạn – Subtask 1, 2
Ở cách 1, khi $j$ tăng thêm 1, ta lại cộng lại từ đầu $a_i + \ldots + a_j$ – rất phí. Thay vào đó, giữ biến s là tổng $a_i..a_j$, mỗi lần kéo dài đoạn chỉ cần s += a[j]. Mất đi một vòng lặp, còn $O(n \cdot R) \le O(n^2)$.
Kết quả chạy thật: bản C++ đúng 65/100 test (quá thời gian ở test 61, 63, 67, 69–100), test đúng chạy lâu nhất 0.80s; bản Python (chỉ chạy test 1–80) đúng 45/80 test (quá thời gian ở test 36, 38, 40–41, 43–44, 46–48, 50, 52–55, 59, 61–80), test đúng lâu nhất 0.95s. Ăn trọn subtask 1 và 2. Ở subtask 3, các test 61–70 có $R$ không quá lớn nên vài test vẫn qua, còn các test 71–100 có $L = 1$, $R = n = 10^5$ thì phải duyệt khoảng $5 \cdot 10^9$ cặp $(i, j)$ – quá thời gian.
Cách 3Tổng tiền tố + multiset – Full điểm
Cài đặt đúng ý tưởng ở trên: tính mảng p, rồi trượt cửa sổ $[j - R, j - L]$ với một multiset.
ms.insert(p[j - L]): chỉ số $i = j - L$ vừa đủ xa để đoạn $a_{i+1..j}$ dài đúng $L$.if (j - R - 1 >= 0) ms.erase(ms.find(p[j - R - 1])): chỉ số $i = j - R - 1$ cho đoạn dài $R + 1$ – vừa vượt quá giới hạn nên phải bỏ đi. Mỗi giá trị được thêm 1 lần và xoá tối đa 1 lần.*ms.begin()là phần tử nhỏ nhất của multiset (luôn có ít nhất 1 phần tử vì vừa thêm vào).- Bản Python: Python không có
multisetsẵn nên mình dùngheapqlưu cặp $(p_i, i)$. Khi đỉnh heap có chỉ số $i < j - R$ (đã ra khỏi cửa sổ) thì mới bỏ đi – gọi là xoá lười: phần tử cũ nằm dưới đáy heap không làm sai kết quả nên cứ để đó.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.04s; bản Python đúng 100/100 test, test đúng lâu nhất 0.26s.
Mở rộng: thay multiset bằng hàng đợi hai đầu đơn điệu (deque giữ các chỉ số có $p$ tăng dần) sẽ được $O(n)$. Nhưng với $n = 10^5$ thì multiset $O(n \log n)$ đã quá đủ, lại dễ viết và dễ hiểu hơn.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Test đúng lâu nhất | Ghi chú |
|---|---|---|---|---|
| 1. Vét cạn $O(n^3)$ | C++ | 51/100 | 0.96s | Quá thời gian test 36, 38, 40, 43, 46–48, 52–54, 59, 61–65, 67, 69–100 |
| Python | 38/60 | 0.51s | Chỉ chạy test 1–60; quá thời gian test 31–33, 36–38, 40–48, 51–54, 56, 58–59 | |
| 2. Cộng dồn $O(n \cdot R)$ | C++ | 65/100 | 0.80s | Quá thời gian test 61, 63, 67, 69–100 |
| Python | 45/80 | 0.95s | Chỉ chạy test 1–80; quá thời gian test 36, 38, 40–41, 43–44, 46–48, 50, 52–55, 59, 61–80 | |
3. Tổng tiền tố + multiset | C++ | 100/100 | 0.04s | Full điểm |
| Python | 100/100 | 0.26s | Full điểm (heapq + xoá lười) |
ans = LLONG_MIN (có test đáp án âm) và dùng long long (đáp án tới $10^{14}$).
Nhận xét
Đăng nhận xét