Hai con trỏ
- Độ khó
- ★★★☆☆ Vừa
- Thời lượng
- Khoảng 90 phút
- Học trước
- Sort, pair và comparator
- Chủ đề
- hai con trỏmảng
- Trạng thái
Kiến thức cơ bản
Vì sao cần hai con trỏ
Hổ xếp n tấm thẻ có ghi số theo thứ tự tăng dần và nhờ bạn tìm hai tấm thẻ có tổng đúng bằng K. Cách đơn giản nhất là thử mọi cặp bằng hai vòng for lồng nhau. Với n = 105, số cặp khoảng 5×109, máy tính phải chạy cả phút mới xong (quy ước máy chạy khoảng 108 phép tính mỗi giây).
Có cách nhanh hơn nhiều: Ta đặt con trỏ l ở tấm thẻ đầu tiên và con trỏ r ở tấm thẻ cuối cùng. Mỗi bước chỉ một con trỏ nhích vào giữa một ô, hai con trỏ gặp nhau là dừng. Tổng cộng không quá n bước, với n = 105 máy chỉ mất một cái chớp mắt. Đó là kỹ thuật hai con trỏ.
- Lưu ý: "con trỏ" ở đây chỉ là biến nguyên lưu chỉ số trong mảng (ví dụ l và r, viết tắt của left và right). Nó không phải là con trỏ địa chỉ bộ nhớ (pointer) trong C++.
Kiểu 1: Hai con trỏ đi ngược chiều
Một con trỏ đứng ở đầu trái (l = 0), một con trỏ đứng ở đầu phải (r = n − 1), cả hai cùng đi vào giữa cho đến khi gặp nhau (l < r không còn đúng). Kiểu này dùng cho các bài về cặp phần tử trên dãy đã sắp xếp và bài về dãy đối xứng.
Ví dụ: tìm hai số có tổng bằng K trên dãy tăng dần
Dãy a = 1 3 4 6 8 11 và K = 10. Hai con trỏ chạy như sau:
Bước 1: 1 3 4 6 8 11 l = 0, r = 5
^ ^
l r
1 + 11 = 12 > 10: tổng lớn quá → giảm r (r--)
Bước 2: 1 3 4 6 8 11 l = 0, r = 4
^ ^
l r
1 + 8 = 9 < 10: tổng nhỏ quá → tăng l (l++)
Bước 3: 1 3 4 6 8 11 l = 1, r = 4
^ ^
l r
3 + 8 = 11 > 10: tổng lớn quá → giảm r (r--)
Bước 4: 1 3 4 6 8 11 l = 1, r = 3
^ ^
l r
3 + 6 = 9 < 10: tổng nhỏ quá → tăng l (l++)
Bước 5: 1 3 4 6 8 11 l = 2, r = 3
^ ^
l r
4 + 6 = 10 = K → tìm thấy cặp!
Vì sao bỏ bớt một con trỏ được?
Khi a[l] + a[r] > K, a[r] là số quá lớn: dù ghép với số nhỏ nhất còn lại là a[l] cũng đã vượt K, còn ghép với số khác thì còn lớn hơn (vì dãy tăng dần). Vậy a[r] chắc chắn không ghép được với ai, ta giảm r mà không bỏ sót đáp án nào. Khi a[l] + a[r] < K thì a[l] là số "vô dụng" và ta tăng l. Nhờ vậy mỗi bước loại bỏ được một phần tử.
Code mẫu
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
long long K;
cin >> n >> K;
vector<long long> a(n);
for (int i = 0; i < n; i++) cin >> a[i]; // a đã tăng dần
int l = 0, r = n - 1; // l: đầu trái, r: đầu phải
bool found = false;
while (l < r) { // hai bạn chưa gặp nhau (không dùng l <= r)
long long tong = a[l] + a[r];
if (tong == K) {
found = true;
break;
} else if (tong < K) {
l++; // tổng nhỏ quá: tăng l để lấy số lớn hơn
} else {
r--; // tổng lớn quá: giảm r để lấy số nhỏ hơn
}
}
cout << (found ? "YES" : "NO");
return 0;
}
Kiểu 2: Hai con trỏ đi cùng chiều
Hai dãy đã sắp xếp giống như hai hàng học sinh xếp theo chiều cao. Mỗi hàng có một con trỏ chỉ vào bạn đứng đầu hàng còn lại. Mỗi bước, ta so sánh hai bạn ở đầu hai hàng rồi cho bạn thấp hơn vào hàng mới, giống như hai hàng răng của chiếc khóa kéo ăn khớp vào nhau. Mỗi con trỏ chỉ đi tới, không bao giờ quay lại.
Ví dụ: gộp hai dãy đã sắp xếp
a = 1 4 7 b = 2 3 9 c (kết quả) = (trống)
i=0, j=0: so sánh a[0]=1 và b[0]=2 → lấy 1 (i++) c = 1
i=1, j=0: so sánh a[1]=4 và b[0]=2 → lấy 2 (j++) c = 1 2
i=1, j=1: so sánh a[1]=4 và b[1]=3 → lấy 3 (j++) c = 1 2 3
i=1, j=2: so sánh a[1]=4 và b[2]=9 → lấy 4 (i++) c = 1 2 3 4
i=2, j=2: so sánh a[2]=7 và b[2]=9 → lấy 7 (i++) c = 1 2 3 4 7
i=3: hàng a đã hết → bê nốt b: lấy 9 c = 1 2 3 4 7 9
Code mẫu
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (int i = 0; i < n; i++) cin >> a[i]; // hàng a tăng dần
for (int j = 0; j < m; j++) cin >> b[j]; // hàng b tăng dần
vector<int> c; // hàng mới sau khi gộp
int i = 0, j = 0; // i: đầu hàng a, j: đầu hàng b
while (i < n && j < m) { // cả hai hàng còn người
if (a[i] <= b[j]) {
c.push_back(a[i]); // bạn ở hàng a thấp hơn: vào trước
i++;
} else {
c.push_back(b[j]);
j++;
}
}
// một hàng đã hết: bê nốt hàng còn lại
while (i < n) { c.push_back(a[i]); i++; }
while (j < m) { c.push_back(b[j]); j++; }
for (int x : c) cout << x << " ";
return 0;
}
Cùng cách nghĩ này giải được nhiều bài khác: tìm các số chung của hai dãy (nếu hai số bằng nhau thì cả hai con trỏ cùng tiến), tìm số chỉ có ở một dãy, hoặc xóa số trùng trong dãy đã sắp xếp (một con trỏ đọc, một con trỏ ghi).
Độ phức tạp
- Hai vòng for lồng nhau thử mọi cặp: khoảng n×n/2 phép, độ phức tạp O(n²). Với n = 105 thì quá chậm.
- Hai con trỏ: mỗi con trỏ chỉ đi một chiều, tổng số bước không quá n (hoặc n + m với hai dãy), độ phức tạp O(n). Với n = 105 chỉ mất một cái chớp mắt.
- Nếu đề cho dãy chưa sắp xếp mà ta cần sắp xếp trước bằng sort, tổng cộng là O(n log n) vì bước sắp xếp chiếm nhiều thời gian nhất. Vẫn nhanh hơn O(n²) rất nhiều.
Khi nào nghĩ đến hai con trỏ
| Dấu hiệu trong đề | Kiểu con trỏ | Ví dụ |
|---|---|---|
| Tìm cặp phần tử có tổng (hoặc hiệu) cho trước; dãy đã sắp xếp hoặc có thể sắp xếp | Ngược chiều (hoặc cùng chiều với hiệu) | Hai chiếc bánh vừa đủ; Hai cây cách nhau K |
| Dãy đối xứng, đảo ngược dãy, so sánh phần tử đối xứng nhau | Ngược chiều | Tên đối xứng; Đảo ngược đoàn tàu |
| Có hai dãy đã sắp xếp: gộp, lấy phần chung, lấy phần khác | Cùng chiều, mỗi dãy một con trỏ | Hợp nhất hai hàng; Giao của hai đội |
| Duyệt một dãy đã sắp xếp để loại bớt hoặc gom phần tử | Cùng chiều, một con trỏ đọc và một con trỏ ghi | Xóa số trùng |
Những cái bẫy hay gặp
- Quên sắp xếp trước: cách "tổng nhỏ thì tiến l, tổng lớn thì lùi r" chỉ đúng khi dãy đã tăng dần. Nếu đề cho dãy lộn xộn, hãy sort rồi mới dùng hai con trỏ.
- Viết l <= r thay vì l < r khi tìm cặp: khi l = r, ta đang ghép một phần tử với chính nó, kết quả sai.
- Quên di chuyển con trỏ sau khi đã xử lý (ví dụ khi tìm thấy cặp hoặc khi bằng nhau): chương trình lặp mãi không dừng.
- Quên đoạn "bê nốt phần còn lại" khi một dãy hết trước dãy kia (bài gộp).
- Tổng hai số nguyên lên đến 109 có thể vượt quá int, và số cặp có thể lên đến hàng chục tỉ: hãy dùng long long.
Một số hàm hay đi cùng
| sort(a.begin(), a.end()) | Sắp xếp vector a tăng dần. Dùng trước khi áp dụng hai con trỏ ngược chiều trên dãy lộn xộn. |
|---|---|
| swap(a[l], a[r]) | Đổi chỗ hai phần tử. Dùng để đảo ngược dãy bằng hai con trỏ. |
| a.size() | Số phần tử của vector. Chú ý kiểu của nó là số không dấu, nên hãy gán vào biến int n rồi mới tính r = n − 1. |
| c.push_back(x) | Thêm x vào cuối vector c. Dùng để xây dãy kết quả khi gộp hoặc lọc. |
Luyện tập
Bài 1. Đảo ngược đoàn tàu
Thỏ có một đoàn tàu đồ chơi gồm n toa, toa thứ i mang số hiệu a[i]. Hôm nay tàu quay đầu nên thứ tự các toa bị đảo ngược. Hãy in ra số hiệu các toa sau khi quay đầu. Gợi ý: để Po đứng ở toa đầu, Thỏ đứng ở toa cuối rồi hai bạn đổi chỗ cho nhau, sau đó cùng bước vào giữa.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | n số nguyên sau khi đảo ngược, cách nhau bởi dấu cách. | |
| Test | Input | Output |
| 1 | 5 1 2 3 4 5 | 5 4 3 2 1 |
| 2 | 4 10 20 30 40 | 40 30 20 10 |
Bài 2. Tên đối xứng
Hổ rất thích những cái tên đối xứng, tức là đọc từ trái sang phải hay từ phải sang trái đều giống nhau (ví dụ level, abba). Cho một xâu s, hãy cho Hổ biết xâu đó có đối xứng hay không.
| Đầu vào | Một dòng chứa xâu s gồm các chữ cái thường, không có dấu cách (1 ≤ độ dài ≤ 105). | |
|---|---|---|
| Đầu ra | YES nếu xâu đối xứng, ngược lại in NO. | |
| Test | Input | Output |
| 1 | level | YES |
| 2 | abca | NO |
Bài 3. Hai chiếc bánh vừa đủ
Gấu Po có K đồng và muốn mua đúng hai chiếc bánh khác nhau sao cho tiêu hết số tiền. Tiệm có n chiếc bánh, giá được ghi theo thứ tự tăng dần. Mỗi chiếc bánh chỉ có một cái, Po không được mua một chiếc hai lần. Có cách chọn nào không?
| Đầu vào | Dòng 1: hai số nguyên n, K (2 ≤ n ≤ 105, 1 ≤ K ≤ 2×109). Dòng 2: n số nguyên a[i] sắp xếp tăng dần (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | YES nếu có hai chiếc bánh ở hai vị trí khác nhau có tổng giá bằng K, ngược lại in NO. | |
| Test | Input | Output |
| 1 | 6 10 1 3 4 6 8 11 | YES |
| 2 | 4 8 1 4 5 9 | NO |
Bài 4. Đếm cặp đá quý
Hổ xếp n viên đá quý thành một hàng, trọng lượng các viên đá đôi một khác nhau và tăng dần từ trái sang phải. Hổ muốn ghép hai viên đá thành một cặp có tổng trọng lượng đúng bằng K. Hỏi có bao nhiêu cặp như vậy? (Cặp (x, y) và (y, x) chỉ tính một lần.)
| Đầu vào | Dòng 1: hai số nguyên n, K (2 ≤ n ≤ 105, 1 ≤ K ≤ 2×109). Dòng 2: n số nguyên a[i] tăng dần, đôi một khác nhau (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số cặp có tổng bằng K. | |
| Test | Input | Output |
| 1 | 6 10 1 2 3 7 8 9 | 3 |
| 2 | 7 12 2 4 5 6 7 8 10 | 3 |
Bài 5. Hợp nhất hai hàng
Lớp của Thỏ có hai hàng học sinh, mỗi hàng đã xếp theo chiều cao tăng dần. Cô giáo muốn gộp hai hàng thành một hàng duy nhất cũng tăng dần, giống như kéo khóa áo: bạn thấp hơn ở đầu hai hàng sẽ được vào trước. Hãy in chiều cao của hàng sau khi gộp.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 105). Dòng 2: n số nguyên tăng dần (không giảm). Dòng 3: m số nguyên tăng dần (không giảm). Mọi giá trị không quá 109. | |
|---|---|---|
| Đầu ra | n + m số nguyên sau khi gộp, theo thứ tự không giảm, cách nhau bởi dấu cách. | |
| Test | Input | Output |
| 1 | 3 4 1 5 9 2 3 6 10 | 1 2 3 5 6 9 10 |
| 2 | 3 2 1 2 3 7 8 | 1 2 3 7 8 |
Bài 6. Xóa số trùng
Gấu Po có một dãy n số đã sắp xếp không giảm, trong đó có nhiều số bị lặp lại. Po muốn giữ lại mỗi giá trị đúng một lần, vẫn theo thứ tự cũ. Hãy giúp Po. Gợi ý: một con trỏ đi đọc từng số, một con trỏ chỉ chỗ ghi số mới.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên không giảm (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Dãy sau khi bỏ các số trùng, cách nhau bởi dấu cách. | |
| Test | Input | Output |
| 1 | 8 1 1 2 2 2 3 5 5 | 1 2 3 5 |
| 2 | 3 4 4 4 | 4 |
Bài 7. Hai củ cà rốt nhẹ
Thỏ có n củ cà rốt, củ thứ i nặng a[i] gam. Thỏ muốn chọn ra hai củ khác nhau để bỏ vào một cái giỏ có sức chứa K gam, tức là tổng khối lượng hai củ không vượt quá K. Hỏi Thỏ có bao nhiêu cách chọn cặp củ cà rốt? (Dãy chưa sắp xếp.)
| Đầu vào | Dòng 1: hai số nguyên n, K (2 ≤ n ≤ 2×105, 1 ≤ K ≤ 2×109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số cặp chỉ số (i, j) với i < j thỏa a[i] + a[j] ≤ K. Chú ý đáp án có thể rất lớn. | |
| Test | Input | Output |
| 1 | 5 8 5 1 4 2 3 | 9 |
| 2 | 4 3 2 2 2 2 | 0 |
Bài 8. Giao của hai đội
Đội cờ vua của Hổ có n bạn, đội cờ tướng có m bạn. Mỗi bạn có một mã số riêng, danh sách mã của mỗi đội được ghi tăng dần. Hãy liệt kê mã số của những bạn tham gia cả hai đội.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 105). Dòng 2: n số nguyên tăng dần, đôi một khác nhau. Dòng 3: m số nguyên tăng dần, đôi một khác nhau. Mọi mã số không quá 109. | |
|---|---|---|
| Đầu ra | Các mã số chung theo thứ tự tăng dần, cách nhau bởi dấu cách. Nếu không có mã nào chung, in KHONG. | |
| Test | Input | Output |
| 1 | 5 4 1 3 5 7 9 3 4 7 10 | 3 7 |
| 2 | 3 3 1 2 3 4 5 6 | KHONG |
Bài 9. Hai món quà gần đủ
Gấu Po cần mua hai món quà khác nhau cho Thỏ với số tiền lý tưởng là K đồng. Cửa hàng có n món quà (chưa sắp xếp), giá món thứ i là a[i]. Po muốn tổng giá hai món quà gần với K nhất có thể. Hãy tính độ chênh lệch nhỏ nhất giữa tổng giá hai món quà và K.
| Đầu vào | Dòng 1: hai số nguyên n, K (2 ≤ n ≤ 105, 1 ≤ K ≤ 2×109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Giá trị nhỏ nhất của |a[i] + a[j] − K| với i ≠ j. | |
| Test | Input | Output |
| 1 | 5 20 3 9 12 5 14 | 1 |
| 2 | 3 100 1 2 3 | 95 |
Bài tập tự luyện
Bài 1. Sửa dãy thành đối xứng
Thỏ có một dãy n số. Thỏ muốn dãy này đọc từ trái sang phải hay từ phải sang trái đều giống nhau. Mỗi lần, Thỏ được đổi giá trị của một phần tử thành số bất kỳ. Hỏi Thỏ cần đổi ít nhất bao nhiêu phần tử?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số lần đổi ít nhất. | |
| Test | Input | Output |
| 1 | 4 1 2 3 4 | 2 |
| 2 | 5 7 8 9 8 7 | 0 |
Bài 2. Chia kẹo hai đầu
Hổ xếp n viên kẹo thành một hàng, viên thứ i nặng w[i] gam. Gấu Po ăn từ đầu trái của hàng, Thỏ ăn từ đầu phải của hàng. Mỗi lượt, bạn nào đang có tổng khối lượng kẹo đã ăn ít hơn thì được lấy viên kẹo ở đầu hàng phía mình (nếu hai bạn bằng nhau thì Po được lấy trước). Cứ thế cho đến khi hết kẹo. Hỏi mỗi bạn ăn bao nhiêu viên?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên w[i] (1 ≤ w[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Hai số nguyên: số viên của Po và số viên của Thỏ, cách nhau bởi dấu cách. | |
| Test | Input | Output |
| 1 | 5 3 1 4 1 5 | 3 2 |
| 2 | 4 2 2 2 2 | 2 2 |
Bài 3. Gộp rồi bỏ trùng
Gấu Po có hai danh sách mã số học sinh, mỗi danh sách đã được sắp xếp không giảm và có thể có mã bị ghi lặp. Po muốn lập danh sách chung gồm mọi mã xuất hiện ở ít nhất một danh sách, mỗi mã chỉ ghi một lần và theo thứ tự tăng dần.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 105). Dòng 2: n số nguyên không giảm. Dòng 3: m số nguyên không giảm. Mọi giá trị không quá 109. | |
|---|---|---|
| Đầu ra | Danh sách chung theo thứ tự tăng dần, cách nhau bởi dấu cách. | |
| Test | Input | Output |
| 1 | 4 3 1 2 2 5 2 3 5 | 1 2 3 5 |
| 2 | 2 2 7 7 7 7 | 7 |
Bài 4. Chỉ có ở đội A
Đội A của Hổ có n bạn, đội B có m bạn, mã số mỗi đội được ghi tăng dần và không lặp. Hổ muốn biết những bạn nào chỉ có ở đội A mà không có ở đội B. Hãy liệt kê mã số của họ.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 105). Dòng 2: n số nguyên tăng dần, đôi một khác nhau. Dòng 3: m số nguyên tăng dần, đôi một khác nhau. Mọi mã số không quá 109. | |
|---|---|---|
| Đầu ra | Các mã số chỉ thuộc đội A theo thứ tự tăng dần, cách nhau bởi dấu cách. Nếu không có mã nào, in KHONG. | |
| Test | Input | Output |
| 1 | 5 3 1 2 4 6 8 2 6 7 | 1 4 8 |
| 2 | 2 4 1 2 1 2 3 9 | KHONG |
Bài 5. Hai cây cách nhau K
Dọc đường đi, Thỏ trồng n cây, cây thứ i nằm ở vị trí a[i] mét tính từ cổng (các vị trí tăng dần, đôi một khác nhau). Thỏ muốn biết có bao nhiêu cặp cây cách nhau đúng K mét.
| Đầu vào | Dòng 1: hai số nguyên n, K (2 ≤ n ≤ 105, 1 ≤ K ≤ 109). Dòng 2: n số nguyên a[i] tăng dần (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số cặp (i, j) với i < j và a[j] − a[i] = K. | |
| Test | Input | Output |
| 1 | 6 3 1 2 4 5 7 8 | 4 |
| 2 | 4 10 1 2 3 4 | 0 |
Bài 6. Bộ ba may mắn
Hổ có n tấm thẻ ghi các số tăng dần, đôi một khác nhau. Một bộ ba thẻ được gọi là may mắn nếu tổng ba số trên thẻ đúng bằng K. Hỏi có bao nhiêu bộ ba may mắn? Gợi ý: cố định tấm thẻ đầu tiên, rồi dùng hai con trỏ tìm hai tấm còn lại. Độ phức tạp mong muốn là O(n²).
| Đầu vào | Dòng 1: hai số nguyên n, K (3 ≤ n ≤ 2000, 1 ≤ K ≤ 3×109). Dòng 2: n số nguyên a[i] tăng dần, đôi một khác nhau (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số bộ ba chỉ số i < j < k thỏa a[i] + a[j] + a[k] = K. | |
| Test | Input | Output |
| 1 | 6 12 1 2 3 4 5 6 | 3 |
| 2 | 4 100 1 2 3 4 | 0 |
Bài 7. Hồ chứa nước
Gấu Po dựng n cột hàng rào thẳng đứng cạnh nhau, hai cột liền kề cách nhau 1 mét, cột thứ i cao h[i] mét. Po chọn hai cột bất kỳ làm hai bờ của một cái hồ, mực nước tối đa bằng cột thấp hơn. Lượng nước chứa được bằng (chiều cao cột thấp hơn) × (khoảng cách hai cột). Hãy tìm lượng nước lớn nhất mà một cái hồ có thể chứa. Gợi ý: bắt đầu với hai cột ngoài cùng, mỗi bước nên bỏ cột nào?
| Đầu vào | Dòng 1: số nguyên n (2 ≤ n ≤ 105). Dòng 2: n số nguyên h[i] (1 ≤ h[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Lượng nước lớn nhất (có thể vượt quá phạm vi kiểu int). | |
| Test | Input | Output |
| 1 | 9 1 8 6 2 5 4 8 3 7 | 49 |
| 2 | 2 5 5 | 5 |
Bài 8. Thuyền cứu hộ
Hổ lái thuyền cứu hộ đưa n người qua sông, người thứ i nặng a[i] kg. Mỗi thuyền chở được tối đa hai người và tổng cân nặng không vượt quá W kg. Mỗi người đều nhẹ hơn hoặc bằng W. Hỏi Hổ cần ít nhất bao nhiêu chuyến thuyền? Gợi ý: nên ghép người nặng nhất với người nhẹ nhất.
| Đầu vào | Dòng 1: hai số nguyên n, W (1 ≤ n ≤ 105, 1 ≤ W ≤ 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ W). | |
|---|---|---|
| Đầu ra | Số chuyến thuyền ít nhất. | |
| Test | Input | Output |
| 1 | 4 6 3 5 3 4 | 3 |
| 2 | 3 10 1 2 3 | 2 |
Bài 9. Thử thách: Đoạn liên tiếp có tổng K
Gấu Po viết n số dương thành một hàng. Po muốn đếm xem có bao nhiêu đoạn liên tiếp (một dãy các số đứng cạnh nhau) có tổng đúng bằng K. Gợi ý: vì mọi số đều dương nên khi thêm số mới vào bên phải thì tổng chỉ tăng. Hãy để một con trỏ đánh dấu đầu bên trái của đoạn và một con trỏ đánh dấu đầu bên phải. Đây cũng là bài chuẩn bị cho tuần sau về cửa sổ trượt.
| Đầu vào | Dòng 1: hai số nguyên n, K (1 ≤ n ≤ 2×105, 1 ≤ K ≤ 1014). Dòng 2: n số nguyên dương a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số đoạn liên tiếp [l, r] có tổng a[l] + ... + a[r] = K. | |
| Test | Input | Output |
| 1 | 5 7 2 5 2 3 4 | 3 |
| 2 | 6 3 1 2 1 2 1 2 | 5 |
- Gợi ý chung: Trước khi code, hãy tự hỏi ba câu: (1) Dãy đã sắp xếp chưa, hay mình cần sort trước? (2) Có cần hai con trỏ đi ngược chiều từ hai đầu, hay mỗi dãy một con trỏ đi cùng chiều? (3) Mỗi bước nên di chuyển con trỏ nào, và vì sao làm vậy không bỏ sót đáp án? Hãy chạy tay trên một ví dụ nhỏ, viết ra giá trị của l, r (hoặc i, j) sau mỗi bước. Với các bài đếm, nhớ dùng long long. Bài Thử thách cuối cùng chính là bước đệm sang tuần sau: hai con trỏ cùng chiều, một con trỏ đứng đầu đoạn và một con trỏ đứng cuối đoạn, gọi là cửa sổ trượt.