Kỹ thuật 2 con trỏ & Bài tập vận dụng

--- title: Kỹ thuật 2 con trỏ & Bài tập vận dụng --- Kỹ thuật 2 con trỏ & Bài tập vận dụng === ----- ###### ✍️ Author: 2School Guideline ###### 📋 Content: [TOC] ----- # Lời mở đầu Bài viết này sẽ giúp bạn hiểu thêm về **kỹ thuật 2 con trỏ**. Đây là một kỹ thuật được dùng khá phổ biến, giúp tiết kiệm thời gian và không gian xử lí. Với **kỹ thuật 2 con trỏ** chúng ta sẽ sử dụng hai con trỏ để di chuyển trên một danh sách/mảng/chuỗi để thực hiện các thao tác tìm kiếm trong một vòng lặp trên cấu trúc dữ liệu. Nó bao gồm hai biến thể: - 2 con trỏ cùng chiều - 2 con trỏ ngược chiều ----- # 2 con trỏ cùng chiều ## Định nghĩa Đối với 2 con trỏ cùng chiều, mỗi con trỏ đều bắt đầu ở đầu mảng, di chuyển theo cùng một hướng cho đến khi thỏa một điều kiện nhất định nào đó. Để dễ hiểu hơn, chúng ta hãy cùng lấy 2 bài toán sau làm ví dụ nhé! ## Bài toán 1 Cho lần lượt 2 số nguyên dương $n$, $k$ và mảng $a$ có $n$ phần tử, hãy tìm tổng lớn nhất trong các **dãy con liên tiếp độ dài k** trong mảng. **Giới hạn:** $1\leq k\leq n\leq10^6$, $0\leq|a_i|\leq10^9$. - **Input:** $n$, $k$ và mảng $a$: 8 4 0 9 3 8 2 4 0 9 - **Output:** Kết quả bài toán - tổng lớn nhất trong các dãy con liên tiếp độ dài $k$ : 22 ### Lời giải Ở bài này, chúng ta không thể chạy tính tổng của từng dãy một rồi lấy max với độ phức tạp $O(k\cdot(n-k+1))$ được vì sẽ bị quá thời gian. Ta có thể dùng 2 cách hiệu quả hơn như sau: **Cách 1:** Sử dụng mảng cộng dồn. Các bạn có thể tham khảo qua bài viết của chúng mình về mảng cộng dồn tại [đây](https://www.facebook.com/groups/2sgtinpublic/posts/571943714759103/). Độ phức tạp của cách này là $O(n)$. **Cách 2:** Cách sử dụng đến 2 con trỏ cùng chiều. Để dễ phân tích, ta gọi: - $l, r$ là điểm đầu và điểm cuối của đoạn con đang xét. - $sum(l, r)$ là tổng các phẩn tử trong đoạn $[l, r]$ Kết quả của bài toán sẽ là $max(sum(l, r))$, với $1\leq l\leq r\leq n$ và $r-l+1=k$ Ta sẽ lần lượt xét các đoạn con liên tiếp độ dài k theo thứ tự từ thấp lên cao. Hãy cùng xem cách giải qua ví dụ sau đây: Cho dãy $a=[0,9,3,8,2,4,0,9]$ và $k=4$ - Lúc đầu, $l$ và $r$ đều xuất phát từ vị trí số 1, lúc này ta đang xét mảng gồm 1 phần tử là $a_1$: - $a=[$$0$$,9,3,8,2,4,0,9]$ - $sum(l,r)=0$ - Để đoạn đang xét có đủ $k$ phần tử thì ta tăng $r$ lên đến $k$ và đồng thời mỗi lần tăng $r$, ta cộng biến mới được thêm vào $sum$ và cuối cùng gán biến $sum$ đó vào biến $maxSum$ - tổng lớn nhất của các đoạn con liên tiếp có độ dài $k$ - vì ta mới xét được đoạn con liên tiếp đầu tiên nên tổng này ở thời điểm đó. Ở đây khi tăng $r$ lên $k=4$, ta được: - $a=[$$0,9,3,8$$,2,4,0,9]$ - $sum(l,r)=20$ - $maxSum=20$ - Để lấy được các dãy con tiếp theo mà vẫn giữ nguyên được độ dài k, ta thực hiện thêm biến tiếp theo và bỏ biến cuối cùng của dãy đang xét, đồng thời điều chỉnh lại $sum$ và $maxSum$: - Lần 1: - $a=[0,$$9,3,8,2$$,4,0,9]$ - $sum(l,r)=20-0+2=22$ - $maxSum=22$ - Lần 2: - $a=[0,9,$$3,8,2,4$$,0,9]$ - $sum(l,r)=22-9+4=17$ - $maxSum=22$ - Lần 3: - $a=[0,9,3,$$8,2,4,0$$,9]$ - $sum(l,r)=17-3+0=14$ - $maxSum=22$ - Lần 4: - $a=[0,9,3,8,$$2,4,0,9$$]$ - $sum(l,r)=14-8+9=15$ - $maxSum=22$ - Lúc này, $r=n$ nên không có phần tử nào ở sau để thêm và và không tăng được nữa, vòng lặp kết thúc. - Kết quả của bài toán là $maxSum = 22$. ### Code mẫu ```cpp= #include <bits/stdc++.h> #define ll long long using namespace std; const int maxN = 1e6 + 10; ll a[maxN], sum = 0; int n; ll maxSubarraySum(int k){ ll res = sum; int l = 1, r = k; while (r <= n){ //Vòng lặp kết thức khi không thể lặp lại quá trình thêm và bỏ phần tử r++; //Thêm phần tử vào dãy đang xét sum = sum + a[r] - a[l]; l++; //Bỏ phần tử đầu tiên của dãy đang xét để đảm bảo dãy đang xét vẫn là dãy con liên tiếp có độ dài k res = max(res,sum); //Lấy tổng lớn nhất } return res; //Trả kết quả } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int k; cin >> n >> k; for (int i = 1; i <= n; i++) { cin >>a[i]; if (i <= k) sum += a[i]; } cout << maxSubarraySum(k); return 0; } ``` Ở đây $r$ được tăng từ $1$ đến $n$, $l$ và $sum$ cũng thay đổi đồng thời nên độ phức tạp có thể xem như $O(n)$. ## Bài toán 2 Cho hai dãy số nguyên đã được **sắp xếp không giảm** $a$ và $b$ lần lượt có $n$ và $m$ phần tử. Hãy ghép chúng thành dãy được bố trí theo **thứ tự không giảm**. Giới hạn: $n,m\leq10^5$ và $0\leq a_i,b_i\leq10^9$ - **Input:** $n$, $m$ và 2 mảng $a$, $b$: 5 6 1 3 6 8 10 2 6 7 12 14 15 - **Output:** Mảng kết quả: 1 2 3 6 6 7 8 10 12 14 15 ### Lời giải Gọi mảng kết quả của bài toán là mảng $c$. Đầu tiên, ta hãy cùng xác định phần tử đầu tiên của mảng $c$. Vì mảng $c$ là mảng không giảm nên phần tử đầu tiên của mảng $c$ là phần tử nhỏ nhất trong 2 mảng $a$ và $b$. Mảng $a$ và $b$ đã được sắp xếp không giảm, vì thế phẩn tử nhỏ nhất trong 2 mảng là $a_1$ và $b_1$. Dùng test mẫu để làm ví dụ: - $a=[$$1$$,3,6,8,10]$ - $b=[$$2$$,6,7,12,14,15]$ - $c=[]$ Để lấy được phần tử thứ 2, ta cứ lặp lại việc lấy phần tử nhỏ nhất còn lại trong 2 mảng. Phần tử nào đã được lấy rồi thì ta sẽ cho phần tử tiếp theo là phần tử nhỏ nhất của mảng Như vậy ta có thể quy về việc sử dụng 2 con trỏ cùng chiều. Mảng $a$ có con trỏ $i$ và mảng $b$ có con trỏ $j$ cùng xuất phát từ đầu của 2 mảng. Ví dụ khi làm thao tác này trên test mẫu: - Lúc chọn phần tử đầu tiên của $c$, $a_1$ đã được chọn nên phần tử bé nhất của $b$ lúc này là $a_2$, con trỏ $i$ đi lên: - $a=[1,$$3$$,6,8,10]$ - $b=[$$2$$,6,7,12,14,15]$ - $c=[$$1$$]$ - $b_1$ đã được chọn nên con trỏ $j$ đi lên: - $a=[1,$$3$$,6,8,10]$ - $b=[2,$$6$$,7,12,14,15]$ - $c=[$$1,2$$]$ - $a_2$ đã được chọn nên con trỏ $i$ đi lên: - $a=[1,3,$$6$$,8,10]$ - $b=[2,$$6$$,7,12,14,15]$ - $c=[$$1,2,3$$]$ - $a_3$ đã được chọn nên con trỏ $i$ đi lên: - $a=[1,3,6,$$8$$,10]$ - $b=[2,$$6$$,7,12,14,15]$ - $c=[$$1,2,3,6$$]$ - $b_2$ đã được chọn nên con trỏ $j$ đi lên: - $a=[1,3,6,$$8$$,10]$ - $b=[2,6,$$7$$,12,14,15]$ - $c=[$$1,2,3,6,6$$]$ - $b_3$ đã được chọn nên con trỏ $j$ đi lên: - $a=[1,3,6,$$8$$,10]$ - $b=[2,6,7,$$12$$,14,15]$ - $c=[$$1,2,3,6,6,7$$]$ - $a_4$ đã được chọn nên con trỏ $i$ đi lên: - $a=[1,3,6,8,$$10$$]$ - $b=[2,6,7,$$12$$,14,15]$ - $c=[$$1,2,3,6,6,7,8$$]$ - Mảng $a$ đã được chọn hết nên ta gắn hết phần còn lại của $b$ theo thứ tự vào cuối mảng $c$. Cuối cùng, ta được mảng $c=[$$1,2,3,6,6,7,8,10,12,14,15$$]$. ![Minh họa cách làm bài](https://imgur.com/ZVXyx2n.gif)(Nguồn: VNOI Wiki: https://vnoi.info/wiki/algo/basic/two-pointers.md) ### Code mẫu ```cpp= #include <bits/stdc++.h> using namespace std; const int N=1e5+10; int m,n,a[N],b[N]; vector<int> c; void solve(){ int i = 1, j = 1; while (i <= n || j <= m){ if (j == m + 1 || (i <= n && a[i] <= b[j])) c.push_back(a[i++]); else c.push_back(b[j++]); } for (int i = 0; i < (int)c.size(); i++) cout <<c[i]<<' '; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 1; i <=n; i++) cin >> a[i]; for (int i = 1; i <=m; i++) cin >> b[i]; solve(); return 0; } ``` --- Ở đây 2 con trỏ $i$ và $j$ luôn tăng cho đến khi xét tới giá trị cuối cùng của cả 2 mảng nên số lần $i$ và $j$ tăng sẽ bằng với tổng số phần tử của 2 mảng. Vậy độ phức tạp là $O(n+m)$. # 2 con trỏ ngược chiều ## Định nghĩa - Mỗi con trỏ được đặt ở hai đầu của mảng và chúng di chuyển ngược chiều nhau cho đến khi gặp nhau hoặc thỏa mãn một số điều kiện. ## Bài toán 1 Cho chuỗi $S$ có $n$ ký tự in thường, kiểm tra xem chuỗi $S$ có phải là chuỗi **Palindrome** hay không? Chuỗi **Palindrome** là chuỗi mà khi viết từ trái sang phải hay từ phải sang trái đều không thay đổi (bao gồm chuỗi rỗng). - **Input**: - Số nguyên $n$ ($n ≤ 10^6$). - Chuỗi $S$ có độ dài $n$. - **Output**: - Nếu chuỗi $S$ là chuỗi Palindrome thì in ra "YES", ngược lại thì in ra "NO". - **Ví dụ** | Input | Output | |-------|--------| |7 | | |racecar| YES | | Input | Output | |-------|--------| |4 | | |brub |NO | ### Lời giải - Điều kiện để $1$ chuỗi là palindrome : $s[i] = s[n - i - 1]$ với mọi $i$ trong đoạn $[0, n-1]$ (khi này mình đang xét phần tử bắt đầu là $0$). - Sử dụng $2$ con trỏ ngược chiều, một con trỏ $i$ chạy từ đầu chuỗi đến cuối chuỗi, $1$ con trỏ $j$ chạy từ cuối chuỗi đến đầu chuỗi, thao tác duyệt chuỗi dừng lại khi $i ≥ j$. - Ở mỗi vị trí mà $2$ con trỏ đi qua, kiểm tra xem nếu $S[i] ≠ S[j]$ thì trả về kết quả sai; nếu không tìm thấy kết quả sai, trả về kết quả đúng. - Độ phức tạp: $O(n)$ - Minh hoạ với test ví dụ: - $i = 0, j = 3$: - $S=[$$b$$,r,u,$$b$$]$ - Khi này $S[i] = S[j]$ nên mình tăng $i$ lên $1$, đồng thời giảm $j$ đi $1$ và tiếp tục xét. - $i = 1, j = 2$: - $S=[b,$$r$$,$$u$$, b]$ - Khi này, $S[i] ≠ S[j]$ nên mình trả về kết quả **sai**. ### Code mẫu ```cpp= #include <bits/stdc++.h> using namespace std; int n; string S; bool Palindrome(){ int i = 0, j = n - 1; while(i <= j){ if(S[i] != S[j]) { return false; } ++i, --j; } return true; } int main(){ cin >> n; cin >> S; if(Palindrome()) cout << "YES"; else cout << "NO"; return 0; } ``` ## Bài toán 2 Cho mảng $a[]$ có $n$ phần tử được **sắp xếp tăng dần**, tìm vị trí của $2$ phần tử $i, j$ **khác nhau** sao cho tổng của chúng đúng bằng $k$. Dữ liệu đầu vào đảm bảo tồn tại cặp $(i,j)$ có $a[i] + a[j] =k$. Giới hạn: $n ≤ 10^6$$, 0 ≤ a[i] ≤ 10^6$$, 0 ≤ k ≤ 2*10^6$ - **Input**: - $2$ số nguyên ($n ≤ 10^6$, $0 ≤ k ≤ 2\cdot10^6$). - Dòng tiếp theo chứa mảng $a$ có $n$ phần tử ($0 ≤ a[i] ≤ 10^6$). - **Output**: - Dòng duy nhất chứa $2$ số nguyên là $2$ vị trí $i, j$. - **Ví dụ** |Input|Output| |-----|------| |5 7 || |1 2 3 4 5|2 5 | ### Lời giải - Nhận thấy rằng vì mảng có tính chất tăng dần, do đó có thể sử dụng $2$ con trỏ ngược chiều để tìm $2$ phần tử tổng đúng bằng $k$. - Khởi tạo $2$ con trỏ $i$ để duyệt từ đầu đến cuổi mảng và con trỏ $j$ để duyệt từ cuối đến đầu mảng, thao tác duyệt dừng khi $i ≥ j$. - Đối với mỗi cặp $(i, j)$, mình có thể thấy rằng có $3$ trường hợp xảy ra: - **Trường hợp 1: $a[i] + a[j] > k$** - Vì tổng của $2$ phần tử lớn hơn $k$, do đó mình cần giảm tổng của chúng lại bằng cách trừ $j$ đi $1$ (vì mảng $a$ tăng dần, con trỏ $j$ chạy từ cuối mảng nên khi này mình giảm được giá trị của $a[j]$). - **Trường hợp 2: $a[i] + a[j] < k$** - Với ý tưởng tượng tự, khi này mình tăng $i$ lên $1$ để tăng tổng của chúng. - **Trường hợp 3: $a[i] + a[j] = k$** - Khi này, mình đã tìm được cặp $(i,j)$ thoả yêu cầu đề bài, vậy nên chỉ cần xuất ra cặp $(i, j)$. - Độ phức tạp: $O(n)$. ### Code mẫu ```cpp= #include <bits/stdc++.h> using namespace std; const int N = 1e6; int n, k; int a[N + 1]; int main(){ cin >> n >> k; for(int i = 1; i <= n; ++i) cin >> a[i]; int i = 1, j = n; while(i < j){ if(a[i] + a[j] > k) --j; else if(a[i] + a[j] < k) ++i; else{ cout << i << " " << j; return 0; } } return 0; } ``` # Bài tập ## Bài 1: [CSES - Apartments](https://cses.fi/problemset/task/1084) Cư dân từ các tỉnh khác nhau đang đổ về thành phố 2SG để sinh sống và họ quyết định mua những căn hộ tại thành phố này để an cư lập nghiệp. Tuy các người nhập cư đến từ những vùng miền khác nhau, nhưng họ lại có một **mức độ chịu đựng $k$** giống nhau. Với họ giá tiền không quan trọng, nhưng họ lại rất kén chọn các căn hộ mà mình ở. Mỗi cư dân thứ i sẽ có “mắt thẩm mỹ” $a_i$. Nếu như mức thẩm mỹ của căn hộ $b$ không nằm trong khoảng chấp nhận được của hộ dân $i$ thì họ sẽ bỏ qua căn nhà đó (khoảng chấp nhận được của hộ dân $i$ là $[ai – k, ai + k]$, đồng nghĩa hộ dân $i$ sẽ chấp nhận căn nhà có mức thẩm mỹ $b$ khi và chỉ khi $a_i – k \leq b \leq a_i + k$ Chính quyền thành phố hiện tại đang phải đón nhận $n$ cư dân và họ hiện tại có $m$ căn hộ. Vì đang thiếu lực lượng lao động cho thành phố nên thành phố yêu cầu bạn, một nhà toán học đại tài, **chia các căn hộ ra sao mà số lượng cư dân quyết định chọn thành phố làm nơi sinh sống là nhiều nhất.** Hãy thể hiện tài năng của bạn nào! - **Input:** - Dòng đầu tiên là $n$, $m$, $k$ lần lượt là số cư dân, số căn hộ và mức độ chịu đựng chung của cư dân. - Dòng tiếp theo là mảng $a$ độ dài $n$ với $a_i$ là "mắt thẩm mỹ" của cư dân thứ $i$. - Dòng cuối cùng là mảng $b$ độ dài $m$ với $b_i$ là "độ thẩm mỹ" của căn hộ thứ $i$. - **Output:** Kết quả bài toán - số cư dân nhiều nhất có được căn hộ nằm trong mức độ chịu đựng. - **Giới hạn:** - $1 \leq n,m \leq 2.10^5$ - $0 \leq k \leq 10^9$ - $1 \leq a_i \leq 10^9$ - **Ví dụ**: - **Input:** 4 3 5 60 45 80 60 30 60 75 - **Output:** 2 ## Bài 2: [VNOJ - VMQUABEO](https://oj.vnoi.info/problem/vmquabeo) ## Bài 3: [VNOJ - NKSGAME](https://oj.vnoi.info/problem/nksgame) ## Bài 4: [CSES - Ferris Wheel](https://cses.fi/problemset/task/1090) Ngày hội trẻ em là ngày hôm nay. Và khu vui chơi 2SG đang đón nhận một lượng lớn các “khách hàng nhí” đến tham quan. Và mặt hàng “hot” nhất hiện nay chính là chiếc vòng đu quay. Hiện tại hàng chờ để chơi vòng đu quay đang có $n$ trẻ em, với cân nặng mỗi em là $w_i$. Bạn đang điều hành trò chơi thì bạn bắt được một cuộc gọi đàm. Và nó đem tới một tin không lành. Do số lượng thiếu nhi chơi đu quay quá nhiều nên chất lượng của các cabin đã bị giảm sút nặng nề. Các cabin bên trong kho cũng không khá khẩm là mấy khi đối thủ cạnh tranh đã làm cho các cabin hư hỏng. Điểm chung của các cabin bây giờ là **chỉ có thể chở được tối đa cân nặng là $x$ và chở được từ 1 đến 2 em**. Và theo bạn tính toán, số lượng cabin sẽ không đủ để đáp ứng cho nhu cầu của tất cả trẻ em tại đây. Và đương nhiên, bạn không muốn trẻ em nào phải khóc vì không thể tận hưởng trò chơi yêu thích này. Với công nghệ tối tân nhất của thế kỷ XXX, các cabin có thể thêm vào ngay tức khắc để tiếp tục vận hành. Tuy thế, phía bên kia bộ đàm cũng nói rằng chỉ nên thêm vào một số lượng cabin nhất định để các cabin sau có thể được sửa chữa kịp thời. Nếu thêm vào quá nhiều cabin thì … hậu quả chắc bạn sẽ biết rồi đấy. Việc bạn bây giờ cần làm là **tính số lượng cabin ít nhất để thêm vào vòng đu quay để đảm bảo lượt chơi tiếp theo sẽ được diễn ra trong khi các cabin còn lại sẽ được sửa chữa**. Ồ nhưng mà hãy nhanh lên đấy, các thiếu nhi hiện tại không thể đợi lâu hơn được đâu ! - **Input:** - Dòng đầu tiên là $n$ và $x$ lần lượt là số trẻ em và trọng lượng tối đa mà 1 cabin chịu được - Dòng tiếp theo là mảng $w$ với $w_i$ là cân nặng của "khách hàng nhí" thứ $i$. - **Output:** Kết quả bài toán - số cabin ít nhất cần cho vào vòng đu quay. - **Giới hạn:** - $1 \leq n \leq 2\cdot10^5$ - $1 \leq x \leq 10^9$ - $1 \leq w_i \leq x$ - **Ví dụ**: - **Input:** 4 10 7 2 3 9 - **Output:** 3 ## Bài 5: [CSES - Sum of Two Values](https://cses.fi/problemset/task/1640) Bạn được cho một mảng $a$ gồm $n$ **số nguyên dương**. Nhiệm vụ của bạn là **tìm 2 giá trị (ở hai vị trí khác nhau) sao cho tổng của chúng sẽ bằng $x$**. - **Input:** - Dòng đầu tiên là $n$ và $x$ lần lượt là kích thước của mảng và tổng mong muốn tìm. - Dòng tiếp theo là mảng $a$ có $n$ số nguyên dương. - **Output:** Kết quả bài toán - vị trí của 2 giá trị có tổng là $x$. Nếu có nhiều kết quả, in 1 cặp bất kỳ. Nếu không tìm được cặp số có tổng đúng bằng $x$, in ra _IMPOSSIBLE_. - **Giới hạn:** - $1 \leq n \leq 2\cdot10^5$ - $1 \leq x,a_i \leq 10^9$ - **Ví dụ**: - **Input:** 4 8 2 7 5 1 - **Output:** 2 4