Cửa sổ trượt
- Độ khó
- ★★★★☆ Khó
- Thời lượng
- Khoảng 120 phút
- Học trước
- Mảng cộng dồn 1 chiều, Hai con trỏ
- Chủ đề
- cửa sổ trượthai con trỏ
- Trạng thái
Kiến thức cơ bản
Vì sao cần cửa sổ trượt
Gấu Po ngồi trên đoàn tàu có n toa. Ô cửa sổ của Gấu Po chỉ nhìn thấy đúng k toa nằm cạnh nhau. Tàu chạy tới đâu thì một toa phía sau khuất khỏi cửa sổ, một toa phía trước hiện ra. Gấu Po muốn biết tổng khối lượng hàng ở k toa đang nhìn thấy, ở mọi vị trí của cửa sổ.
Cách chậm: mỗi khi cửa sổ dịch đi một toa, ta cộng lại từ đầu k toa trong cửa sổ. Có khoảng n lần dịch, mỗi lần k phép cộng, tổng cộng n × k phép. Với n = 105, k = 5 × 104 thì cần khoảng 5 × 109 phép, chậm hơn mức 108 của máy rất nhiều.
Cách nhanh: cửa sổ dịch một bước thì chỉ có một toa ra và một toa vào, các toa còn lại giữ nguyên. Vậy ta chỉ cần sửa tổng bằng đúng hai phép tính. Cả hành trình mất khoảng n bước.
Cửa sổ trượt dùng cho các bài toán về đoạn con liên tiếp của dãy (hoặc xâu): đoạn có độ dài đúng k, đoạn dài nhất, đoạn ngắn nhất, hay đếm số đoạn thỏa một điều kiện nào đó.
Cửa sổ có độ dài cố định k
Ví dụ với n = 6, k = 3, các toa chở 2 5 1 8 3 4. Cửa sổ trượt như sau (phần trong ngoặc vuông là cửa sổ):
chỉ số: 0 1 2 3 4 5
a: 2 5 1 8 3 4 k = 3
[2 5 1] tổng = 2 + 5 + 1 = 8
[5 1 8] tổng = 8 - 2 + 8 = 14
[1 8 3] tổng = 14 - 5 + 3 = 12
[8 3 4] tổng = 12 - 1 + 4 = 15
(mỗi bước: một số ra ở bên trái, một số vào ở bên phải)
Ba bước làm bài: (1) tính tổng cửa sổ đầu tiên; (2) trượt từng bước, phần tử mới là a[i], phần tử cũ là a[i - k]; (3) sau mỗi bước cập nhật đáp án.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<long long> a(n);
for (auto& x : a) cin >> x;
long long sum = 0;
for (int i = 0; i < k; i++) sum += a[i]; // cửa sổ đầu
long long best = sum;
for (int i = k; i < n; i++) {
sum += a[i] - a[i - k]; // a[i] vào, a[i-k] ra
best = max(best, sum); // cập nhật đáp án
}
cout << best; // ví dụ trên: 15
return 0;
}
Cửa sổ có độ dài thay đổi (hai con trỏ l và r)
Bây giờ cửa sổ không còn dài đúng k nữa mà co giãn theo điều kiện của đề. Ta dùng hai chỉ số: l là mép trái và r là mép phải của cửa sổ [l, r]:
- Tăng r (mép phải bước sang phải) để thêm một phần tử vào cửa sổ.
- Nếu cửa sổ bị "quá tải" (vi phạm điều kiện), tăng l (mép trái bước sang phải) để bỏ bớt phần tử bên trái, cho đến khi cửa sổ lại hợp lệ.
- Cả l và r chỉ đi tới, không bao giờ đi lùi.
Ví dụ: tìm đoạn liên tiếp dài nhất có tổng không quá S = 10, với dãy toàn số dương 3 4 2 5 1 6.
a: 3 4 2 5 1 6 S = 10
[3 4 2] tổng 9 <= 10: dài 3
[3 4 2 5] tổng 14 > 10: quá tải
[4 2 5] tổng 11 > 10: vẫn quá
[2 5] tổng 7 <= 10: dài 2
[2 5 1] tổng 8 <= 10: dài 3
[2 5 1 6] tổng 14 > 10: quá tải
[5 1 6] tổng 12 > 10: vẫn quá
[1 6] tổng 7 <= 10: dài 2
Đáp án: 3 (đoạn [3 4 2] hoặc [2 5 1])
int l = 0, best = 0;
long long sum = 0;
for (int r = 0; r < n; r++) {
sum += a[r]; // thêm a[r]
while (sum > S) { // quá tải: tăng l
sum -= a[l]; // bỏ a[l]
l++;
}
best = max(best, r - l + 1); // [l, r] hợp lệ
}
Đoạn ngắn nhất có tổng ít nhất S thì ngược lại: khi cửa sổ đã "đủ" ta ghi nhận độ dài rồi mới thu hẹp cho đến khi không còn đủ.
int l = 0, best = n + 1; // n + 1: chưa tìm thấy
long long sum = 0;
for (int r = 0; r < n; r++) {
sum += a[r];
while (sum >= S) { // còn đủ: ghi nhận
best = min(best, r - l + 1);
sum -= a[l];
l++;
}
}
if (best == n + 1) cout << -1; else cout << best;
Khung chung cho cửa sổ co giãn: thêm a[r] vào cửa sổ; trong khi cửa sổ chưa hợp lệ (hoặc chưa cần thiết) thì bỏ a[l] và tăng l; cuối cùng cập nhật đáp án. Đếm số đoạn cũng làm tương tự: với mỗi r, có đúng r - l + 1 đoạn hợp lệ kết thúc tại r.
Đếm số loại trong cửa sổ bằng mảng đếm
Khi điều kiện nói về "có bao nhiêu loại khác nhau", ta giữ một mảng đếm cnt[] (như đã học ở các tuần trước) và một biến dem là số loại đang có trong cửa sổ.
if (cnt[x] == 0) dem++; // x mới xuất hiện
cnt[x]++; // thêm x vào cửa sổ
cnt[y]--; // bỏ y khỏi cửa sổ
if (cnt[y] == 0) dem--; // y biến mất
Vì sao cách này nhanh
Nhìn vào vòng while nằm trong vòng for, ta dễ tưởng chậm như n × n. Thật ra con trỏ l chỉ tăng chứ không giảm, mà l không thể vượt quá n, nên tổng số lần l++ trong cả chương trình không quá n. Con trỏ r cũng đi không quá n bước. Cả hai cộng lại khoảng 2n bước, gọi là O(n). Với n = 105 máy chỉ mất một cái chớp mắt, trong khi cách thử mọi đoạn cần khoảng 1010 phép.
Các lưu ý quan trọng
- Cửa sổ co giãn theo kiểu l++ chỉ đúng khi thêm phần tử thì tổng chỉ tăng, bớt phần tử thì tổng chỉ giảm, nghĩa là dãy toàn số dương (hoặc điều kiện kiểu đếm). Nếu dãy có số âm thì bỏ bớt phần tử chưa chắc làm tổng giảm, khi đó nên dùng cộng dồn của tuần 13.
- Tổng của nhiều số lớn nên khai báo long long. Số đoạn đếm được (khoảng n²/2) cũng cần long long.
- Thứ tự trong vòng lặp là: thêm a[r], rồi thu hẹp bằng l, rồi mới cập nhật đáp án.
- Cửa sổ cố định cần k ≤ n; kiểm tra chỉ số a[i - k] không bị âm.
Khi nào dùng công cụ nào
| Công cụ | Dùng khi nào | Ví dụ |
|---|---|---|
| Cộng dồn (tuần 13) | Hỏi tổng của nhiều đoạn [l, r] bất kỳ, dãy có thể có số âm | q câu hỏi, mỗi câu cho một đoạn |
| Mảng hiệu (tuần 14) | Cộng thêm một giá trị cho cả một đoạn, nhiều lần | Tưới nước cho các luống từ l đến r |
| Hai con trỏ (tuần 15) | Duyệt dãy từ hai đầu hoặc tìm cặp phần tử | Tìm hai số có tổng bằng K |
| Cửa sổ trượt (tuần 16) | Đoạn liên tiếp dài đúng k, hoặc dài nhất, ngắn nhất, đếm số đoạn thỏa điều kiện | k toa nặng nhất; đoạn dài nhất có tổng không quá S |
Luyện tập
Bài 1. Đoàn tàu của Gấu Po
Đoàn tàu có n toa, toa thứ i chở a[i] ki-lô-gam hàng. Gấu Po ngồi bên cửa sổ và mỗi lúc chỉ nhìn thấy đúng k toa liên tiếp. Tàu chạy qua, Gấu Po muốn biết cửa sổ có lúc nào nhìn thấy tổng khối lượng hàng lớn nhất là bao nhiêu.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ k ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng khối lượng lớn nhất của k toa liên tiếp. | |
| Test | Input | Output |
| 1 | 6 3 2 5 1 8 3 4 | 15 |
| 2 | 3 2 1000000000 1000000000 1000000000 | 2000000000 |
Bài 2. Những ngày mát mẻ
Thỏ ghi lại nhiệt độ của n ngày liên tiếp (có ngày nhiệt độ âm). Thỏ muốn đi nghỉ mát đúng k ngày liên tiếp sao cho tổng nhiệt độ của k ngày đó nhỏ nhất. Hãy tìm ngày bắt đầu chuyến đi. Nếu có nhiều cách thì chọn ngày bắt đầu sớm nhất.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ k ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (-104 ≤ a[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Hai số cách nhau một dấu cách: ngày bắt đầu (đánh số từ 1) và tổng nhiệt độ nhỏ nhất. | |
| Test | Input | Output |
| 1 | 7 3 5 -2 4 -6 1 3 -4 | 2 -4 |
| 2 | 4 2 3 3 3 3 | 1 6 |
Bài 3. Ca làm việc hiệu quả
Hổ quản lý một xưởng bánh trong n ngày, ngày thứ i bán được a[i] chiếc bánh. Một đợt k ngày liên tiếp gọi là "đợt hiệu quả" nếu tổng số bánh bán được trong đợt đó không ít hơn S. Hãy đếm xem có bao nhiêu đợt hiệu quả.
| Đầu vào | Dòng 1: ba số nguyên n, k, S (1 ≤ k ≤ n ≤ 105; 1 ≤ S ≤ 1014). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số đợt k ngày liên tiếp có tổng không nhỏ hơn S. | |
| Test | Input | Output |
| 1 | 6 3 12 2 5 1 8 3 4 | 3 |
| 2 | 4 2 100 1 2 3 4 | 0 |
Bài 4. Cửa sổ nguyên âm
Thỏ viết một xâu s gồm n chữ cái thường lên bảng, rồi dùng một khung bìa che vừa đúng k chữ cái liên tiếp. Thỏ muốn đặt khung ở chỗ nào đó để nhìn thấy nhiều nguyên âm nhất (các nguyên âm là a, e, i, o, u). Hãy cho biết nhiều nhất là bao nhiêu nguyên âm.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ k ≤ n ≤ 105). Dòng 2: xâu s gồm n chữ cái thường. | |
|---|---|---|
| Đầu ra | Số nguyên âm lớn nhất trong k chữ cái liên tiếp. | |
| Test | Input | Output |
| 1 | 9 3 abciiidef | 3 |
| 2 | 5 2 xyzbc | 0 |
Bài 5. Vườn hoa của Hổ
Hổ trồng một hàng n bông hoa, bông thứ i thuộc loại có mã a[i]. Mỗi lần Hổ chỉ ngắm k bông hoa liên tiếp. Hổ thích nhất những lúc nhìn thấy nhiều loại hoa khác nhau. Hãy cho biết trong tất cả các lần ngắm, số loại hoa khác nhau nhiều nhất là bao nhiêu.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ k ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 106). Gợi ý: dùng mảng đếm cnt[a[i]]. | |
|---|---|---|
| Đầu ra | Số loại hoa khác nhau lớn nhất trong k bông liên tiếp. | |
| Test | Input | Output |
| 1 | 7 3 1 2 1 3 3 3 4 | 3 |
| 2 | 5 2 7 7 7 7 7 | 1 |
Bài 6. Chuyến xe chở nặng nhất
Gấu Po có n gói quà xếp thành hàng, gói thứ i nặng a[i]. Chiếc xe đẩy chỉ chở được tổng khối lượng không quá S. Gấu Po muốn lấy các gói quà nằm liên tiếp nhau trên hàng, càng nhiều gói càng tốt. Hỏi lấy được nhiều nhất bao nhiêu gói?
| Đầu vào | Dòng 1: hai số nguyên n, S (1 ≤ n ≤ 105; 1 ≤ S ≤ 1014). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số gói quà liên tiếp nhiều nhất có tổng không quá S (in 0 nếu không lấy được gói nào). | |
| Test | Input | Output |
| 1 | 6 10 3 4 2 5 1 6 | 3 |
| 2 | 3 5 8 9 7 | 0 |
Bài 7. Đoạn đường ngắn nhất
Thỏ muốn gom đủ ít nhất S củ cà rốt. Dọc đường có n luống, luống thứ i có a[i] củ. Thỏ chỉ được hái ở các luống liên tiếp nhau. Hãy tìm số luống ít nhất mà Thỏ phải đi qua để có tổng không ít hơn S củ.
| Đầu vào | Dòng 1: hai số nguyên n, S (1 ≤ n ≤ 105; 1 ≤ S ≤ 1014). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số luống liên tiếp ít nhất có tổng không nhỏ hơn S. Nếu không thể, in -1. | |
| Test | Input | Output |
| 1 | 6 11 1 2 3 4 5 6 | 2 |
| 2 | 3 100 10 20 30 | -1 |
Bài 8. Đếm đoạn kẹo ngoan
Hổ có n túi kẹo xếp thành hàng, túi thứ i có a[i] viên. Một đoạn gồm các túi liên tiếp được gọi là "đoạn ngoan" nếu tổng số kẹo của đoạn không quá S. Hãy đếm xem có bao nhiêu đoạn ngoan (hai đoạn khác nhau nếu khác vị trí đầu hoặc vị trí cuối).
| Đầu vào | Dòng 1: hai số nguyên n, S (1 ≤ n ≤ 105; 1 ≤ S ≤ 1014). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số đoạn liên tiếp có tổng không quá S. Chú ý kết quả có thể rất lớn. | |
| Test | Input | Output |
| 1 | 4 5 1 2 3 4 | 6 |
| 2 | 3 1000000000 1 1 1 | 6 |
Bài 9. Dải ruy băng không lặp màu
Gấu Po có một dải ruy băng ghi bằng xâu s gồm các chữ cái thường, mỗi chữ cái là một màu. Gấu Po muốn cắt một đoạn liên tiếp của dải sao cho không có hai vị trí nào cùng màu. Hỏi đoạn dài nhất cắt được dài bao nhiêu?
| Đầu vào | Một dòng duy nhất: xâu s gồm chữ cái thường, độ dài từ 1 đến 105. | |
|---|---|---|
| Đầu ra | Độ dài lớn nhất của đoạn liên tiếp không có chữ cái nào xuất hiện hai lần. | |
| Test | Input | Output |
| 1 | abcabcbb | 3 |
| 2 | aaaaa | 1 |
Bài tập tự luyện
Bài 1. Đèn lồng sáng liền
Một hàng n chiếc đèn lồng, mỗi chiếc đang sáng (ký tự 1) hoặc tắt (ký tự 0). Thỏ muốn có k đèn liên tiếp đều sáng. Mỗi lần Thỏ bật sáng một đèn đang tắt. Hỏi Thỏ phải bật ít nhất bao nhiêu đèn?
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ k ≤ n ≤ 105). Dòng 2: xâu gồm n ký tự 0 hoặc 1. | |
|---|---|---|
| Đầu ra | Số đèn ít nhất cần bật. | |
| Test | Input | Output |
| 1 | 8 4 10010110 | 1 |
| 2 | 3 2 111 | 0 |
Bài 2. Chia đều bánh
Hổ có n ngày bán bánh, ngày i bán a[i] chiếc. Hổ chọn k ngày liên tiếp và muốn chia đều số bánh bán được cho m bạn nhỏ, không thừa chiếc nào. Hãy đếm xem có bao nhiêu cách chọn k ngày liên tiếp để tổng số bánh chia hết cho m.
| Đầu vào | Dòng 1: ba số nguyên n, k, m (1 ≤ k ≤ n ≤ 105; 1 ≤ m ≤ 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số cách chọn k ngày liên tiếp có tổng chia hết cho m. | |
| Test | Input | Output |
| 1 | 6 3 4 2 5 1 8 3 4 | 2 |
| 2 | 3 3 5 1 2 3 | 0 |
Bài 3. Bậc thang đi lên
Gấu Po đi qua n bậc đá, bậc thứ i cao a[i]. Gấu Po thích các đoạn gồm đúng k bậc liên tiếp mà độ cao tăng chặt (bậc sau cao hơn bậc ngay trước nó). Hãy đếm số đoạn như vậy.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ k ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số đoạn gồm k bậc liên tiếp có độ cao tăng chặt. | |
| Test | Input | Output |
| 1 | 7 3 1 2 3 2 3 4 5 | 3 |
| 2 | 4 2 5 5 5 5 | 0 |
Bài 4. Dãy đèn có thể sửa
Hàng n bóng đèn, bóng hỏng ghi 0, bóng tốt ghi 1. Hổ có thể thay tối đa k bóng hỏng bằng bóng tốt. Sau khi thay, Hổ muốn có dãy bóng tốt liên tiếp dài nhất có thể. Hỏi dãy đó dài bao nhiêu?
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ n ≤ 105; 0 ≤ k ≤ n). Dòng 2: n số a[i], mỗi số là 0 hoặc 1. | |
|---|---|---|
| Đầu ra | Độ dài lớn nhất của dãy bóng tốt liên tiếp. | |
| Test | Input | Output |
| 1 | 10 2 1 1 0 0 1 1 1 0 1 0 | 7 |
| 2 | 4 0 0 0 0 0 | 0 |
Bài 5. Hai màu ruy băng
Thỏ có dải ruy băng ghi bằng xâu s gồm chữ cái thường. Thỏ muốn cắt một đoạn liên tiếp mà chỉ có nhiều nhất hai màu (hai chữ cái khác nhau) xuất hiện trong đoạn. Hỏi đoạn dài nhất dài bao nhiêu?
| Đầu vào | Một dòng duy nhất: xâu s gồm chữ cái thường, độ dài từ 1 đến 105. | |
|---|---|---|
| Đầu ra | Độ dài lớn nhất của đoạn liên tiếp có không quá hai loại chữ cái khác nhau. | |
| Test | Input | Output |
| 1 | abcbbbbcccbdddadacb | 10 |
| 2 | aaa | 3 |
Bài 6. Xếp lại chữ
Gấu Po có xâu s và một xâu mẫu t (gồm chữ cái thường). Gấu Po muốn đếm có bao nhiêu đoạn liên tiếp của s có độ dài bằng |t| mà khi sắp xếp lại các chữ cái thì thành đúng xâu t (nói cách khác, hai xâu có cùng số lượng từng loại chữ cái).
| Đầu vào | Dòng 1: xâu s, độ dài từ 1 đến 105. Dòng 2: xâu t, độ dài từ 1 đến 105. Cả hai xâu gồm chữ cái thường. Gợi ý: dùng hai mảng đếm 26 phần tử. | |
|---|---|---|
| Đầu ra | Số đoạn liên tiếp của s là hoán vị của t (in 0 nếu t dài hơn s). | |
| Test | Input | Output |
| 1 | cbaebabacd abc | 2 |
| 2 | aaaa ab | 0 |
Bài 7. Gom đủ ba màu
Dải đèn của Hổ là xâu s gồm n ký tự, mỗi ký tự chỉ là a, b hoặc c (ba màu đèn). Hổ muốn cắt một đoạn liên tiếp ngắn nhất mà có đủ cả ba màu a, b, c. Hỏi đoạn ngắn nhất dài bao nhiêu?
| Đầu vào | Một dòng duy nhất: xâu s gồm các ký tự a, b, c, độ dài từ 1 đến 105. | |
|---|---|---|
| Đầu ra | Độ dài ngắn nhất của đoạn liên tiếp có đủ ba ký tự a, b, c. Nếu không có đoạn nào, in -1. | |
| Test | Input | Output |
| 1 | abcabc | 3 |
| 2 | aabbaabb | -1 |
Bài 8. Đoạn tổng đúng bằng S
Thỏ có n túi cà rốt xếp thành hàng, túi thứ i có a[i] củ. Hãy đếm xem có bao nhiêu đoạn gồm các túi liên tiếp mà tổng số củ đúng bằng S. (Gợi ý: số đoạn có tổng đúng S bằng số đoạn có tổng không quá S trừ đi số đoạn có tổng không quá S - 1.)
| Đầu vào | Dòng 1: hai số nguyên n, S (1 ≤ n ≤ 105; 1 ≤ S ≤ 1014). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số đoạn liên tiếp có tổng đúng bằng S. Kết quả có thể lớn. | |
| Test | Input | Output |
| 1 | 6 5 1 4 1 2 3 2 | 4 |
| 2 | 3 7 1 2 3 | 0 |
Bài 9. Thử thách: Sơn lại hàng rào
Hàng rào có n tấm ván, mỗi tấm được sơn một màu là một chữ cái thường (xâu s). Gấu Po được sơn lại tối đa k tấm ván, mỗi tấm sơn thành màu tùy ý. Hỏi sau khi sơn, đoạn ván liên tiếp cùng một màu dài nhất có thể dài bao nhiêu? (Gợi ý: đoạn [l, r] làm được khi độ dài đoạn trừ đi số lần xuất hiện của màu nhiều nhất trong đoạn không quá k.)
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ n ≤ 105; 0 ≤ k ≤ n). Dòng 2: xâu s gồm n chữ cái thường (chỉ cần dùng mảng đếm 26 phần tử). | |
|---|---|---|
| Đầu ra | Độ dài lớn nhất của đoạn liên tiếp cùng màu sau khi sơn lại tối đa k tấm ván. | |
| Test | Input | Output |
| 1 | 7 2 abbaabb | 6 |
| 2 | 6 0 abcdef | 1 |
- Gợi ý chung: Đọc đề xong hãy tự hỏi: đoạn có độ dài cố định k hay co giãn? Cố định thì cộng phần tử vào, trừ phần tử ra. Co giãn thì r đi tới, l đi tới và chỉ thu hẹp khi vi phạm. Ba lỗi hay gặp: dùng int cho tổng lớn làm tràn số (hãy thử bài 2 của "Đoàn tàu của Gấu Po" với int), quên cập nhật đáp án sau khi thu hẹp, và dùng cửa sổ co giãn cho dãy có số âm.