---
title: Kỹ thuật 2 con trỏ & Bài tập vận dụng (Hướng dẫn giải bài tập)
---

Kỹ thuật 2 con trỏ & Bài tập vận dụng (Hướng dẫn giải bài tập)
===

-----

###### ✍️ Author: 2School Guideline
###### 📋 Content:

[TOC]

-----

# Bài 1: [CSES - Apartments](https://cses.fi/problemset/task/1084)
## Lời giải
- Để tối ưu được số người dân có nhà ở, chúng ta sẽ xử lí theo kiểu cho người dân với yêu cầu nhỏ thì họ sẽ nhận căn hộ nhỏ.
- Lúc này ta cần sắp xếp lại 2 mảng $a$ và $b$.
- Ta dùng 2 con trỏ $i$ và $j$ lần lượt xuất phát từ đầu 2 mảng $a$ và $b$ để xác định người dân và căn hộ thỏa mãn tương ứng.
- Nếu căn hộ thỏa mãn người dân hiện tại, cư dân đó sẽ lấy căn hộ này và số lượng cư dân có nhà ở tăng lên 1.
- Nếu căn hộ thứ $j$ có độ thẩm mỹ vượt quá mức độ chịu đựng của người dân $i$ thì ta xét đến yêu cầu của người dân $i+1$ - người dân có yêu cầu về thẩm mỹ cao hơn.
- Nếu căn hộ thứ $j$ chưa thỏa yêu cầu của cư dân $i$ thì ta xét đến căn hộ $j+1$ - căn hộ có độ thẩm mỹ cao hơn.
- Độ phức tạp: $O(n \log n + m\log m)$.
## Code mẫu

#include <bits/stdc++.h>
 
using namespace std;

const int N = 2e5 + 10;
int n, m, k, a[N], b[N];

void solve(){
    sort(a, a + n); sort(b, b + m);
    int i, j, ans; i = j = ans = 0;
    while (i < n && j < m)
        if (a[i] - k <= b[j] && b[j] <= a[i] + k){
            ++ans;
            ++i;
            ++j;
        } else if (b[j] < a[i] - k) ++j;
        else ++i;
    cout << ans;
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < m; ++i) cin >> b[i];
    solve();
    return 0;
}

# Bài 2: [VNOJ - VMQUABEO](https://oj.vnoi.info/problem/vmquabeo)
## Lời giải
- Chúng ta hãy cùng nhìn vào một vài yếu tố mà đề đã cho:
- Admin K chỉ chấp nhận đoạn đường từ $[t, p]$ để chạy khi $max(h[t]$ ... $h[p]) - min(h[t]$ ... $h[p]) \leq D$
$=>$ Chúng ta cần một cấu trúc nào đó có khả năng tìm ra min và max của một đoạn nhanh nhất có thể $=>$ **set**
- Đoạn đường $[t, p]$ phải có độ dài tối thiểu là $L$ $=>$ đoạn đường phải có tối thiểu $L + 1$ điểm (nói cách khác, $p - t \geq L$)
- Qua những nhận xét trên, ta có 1 cách làm như sau:
- B1: Gọi con trỏ $t$ và $p$ lần lượt là con trỏ chỉ vị trí trái và phải của đoạn đường mà admin K chọn. Ban đầu con trỏ $t$ chỉ vào vị trí 0.
- B2: Cho con trỏ $p$ tăng đều sao cho tới khi thoả điều kiện $p - t \geq L$. Trong quá trình này, ta đồng thời thêm $h[p]$ vào **set** để tính toán sau.
- B3.1: Nếu như có cặp $[t, p]$ thoả mãn, số đoạn con khác nhau kết thúc ở $p$ thoả mãn yêu cầu $max(h[t]$ ... $h[p]) - min(h[t]$ ... $h[p]) \leq D$ là $p - t - l + 1$. Ta sẽ cộng đáp án vào biến $ans$ ( Vì $p$ tăng đều và mỗi lần ta chỉ lấy các đoạn kết thúc ở $p$ nên ta có thể lấy được tất cả các trường hợp mà không bị trùng đoạn nào. )
- B3.2: Ở trường hợp còn lại khi không có cặp $[t, p]$ thoả mãn nào, chúng ta sẽ tăng con trỏ $t$ lên 1 và xoá đi $h[t]$ trong **set** ( Ta có thể biết con trỏ $t$ luôn tăng chứ không thể giảm vì nếu $h[t] ... h[p]$ đã không thỏa điều kiện thì $h[t] ... h[p+1]$ chắc chắn cũng không thỏa. )
- B4: lặp lại B2 cho tới khi $p = n$
- Đáp án đề bài là $ans$
- Độ phức tạp: $O(n \log n)$.
## Code mẫu

#include <bits/stdc++.h>

using namespace std;

const int N=1e6+10;
int n, l, d, h[N];
long long ans = 0;
multiset<int> s;

void solve(){
    int t = 0, p = -1;
    while (p - t < l) {
        p++;
        s.insert(h[p]);
    }
    while (p < n) {
        int lo = *s.begin(), hi = *s.rbegin();
        if (hi - lo <= d){
            ans += p - t - l + 1;
            p++;
            s.insert(h[p]);
        } 
        else {
            s.erase(s.find(h[t]));
            t++;
            if (p - t < l){
                p++;
                s.insert(h[p]);
            }
        }
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> l >> d;
    for (int i = 0; i < n; i++) cin >> h[i];
    solve();
    return 0;
}

# Bài 3: [VNOJ - NKSGAME](https://oj.vnoi.info/problem/nksgame)
## Lời giải
- **Nhận xét** : để trị tuyệt đối của tổng $2$ phần tử trong $2$ mảng là bé nhất tương đương với việc ta cố gắng lấy $2$ phần tử sao cho tổng của chúng $= 0$.
- Điều này đồng nghĩa với mỗi $b[i]$, mình cần tìm $c[i]$ sao cho $c[i]$ gần với $-b[i]$ nhất.
- Để làm được điều này một cách hiệu quả, mình sẽ sử dụng $2$ con trỏ ngược chiều trên $2$ mảng $b$, $c$ sau khi đã được sắp xếp tăng dần.
- Khởi tạo $1$ con trỏ $i$ chạy từ đầu đến đuôi mảng $b$, con trỏ $j$ chạy từ đuôi đến đầu mảng $c$.
- Với mỗi $b[i]$, mình sẽ dời con trỏ $j$ xuống sao cho trị tuyệt đối của tổng của chúng là bé nhất có thể. Khi trị tuyệt đối của tổng $2$ phần tử là tối ưu (không thể dời con trỏ $j$ xuống để giảm trị tuyết đối của tổng nữa), mình dừng thao tác dời $j$ xuống, đồng thời tăng $i$ để xét vị trí $b[i]$ kế tiếp.
- Độ phức tạp : $O(n \log n)$.
## Code mẫu

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;

int n;
int b[N+1], c[N+1];

void read(){
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> b[i];
    for(int i = 1; i <= n; ++i) cin >> c[i];
    sort(b + 1, b + n + 1);
    sort(c + 1, c + n + 1);
}

void solve(){
    int i = 1, j = n;
    int ans = abs(b[i] + c[j]);
    while(i <= n && j >= 1){
        while(j > 1 && abs(b[i] + c[j-1]) <= abs(b[i] + c[j])) --j;
        ans = min(ans, abs(b[i] + c[j]));
        ++i;
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    read();
    solve();

    return 0;
}

# Bài 4: [CSES - Ferris Wheel](https://cses.fi/problemset/task/1090)
## Lời giải
- Nhận thấy rằng: để tối ưu hoá, với mỗi $a[i]$, chúng ta cần tìm $a[j]$ sao cho $(a[i] + a[j])_m$$_a$$_x$ và $a[i] + a[j] \leq x$.
- Để thực hiện điều này, mình sẽ sử dụng $2$ con trỏ ngược chiều trên mảng $a[]$ đã được sắp xếp tăng dần.
- Khởi tạo con trỏ $i$ đi từ đầu đến cuối mảng, con trỏ $j$ đi từ cuối đến đầu mảng.
- Với mỗi cặp $(i,j)$, sẽ có $2$ trường hợp xảy ra:
- Trường hợp $1$ : $a[i] + a[j] ≤ x$ : khi này cặp $(i, j)$ thoả, ta gom vào $1$ nhóm, đồng thời tăng $i$ lên 1, giảm $j$ đi $1$ để xét $2$ phần tử kế tiếp.
- Trường hợp $2$ : $a[i] + a[j] > x$ : vì cặp $(i, j)$ không thoả, khi này mình cho $a[j]$ vào $1$ nhóm, đồng thời giảm $j$ đi $1$ để có $a[j]$ bé hơn.
- Độ phức tạp : $O(n \log n)$.
## Code mẫu

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5;

int n, x;
int a[N + 1];

void read(){
    cin >> n >> x;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + n + 1);
}

void solve(){
    int ans = 0;
    int i = 1, j = n;
    while(i <= j){
        if(a[i] + a[j] <= x) ++i;
        --j;
        ++ans;
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    read();
    solve();

    return 0;
}

# Bài 5: [CSES - Sum of Two Values](https://cses.fi/problemset/task/1640)
## Lời giải
- Vì đây là $1$ bài toán trong số các bài toán giới thiệu $2$ con trỏ ngược chiều, nên các bạn có thể xem lời giải ở bài viết giới thiệu $2$ con trỏ nhé.
- Độ phức tạp : $O(n \log n)$.
## Code mẫu

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5;

int n, x;
pair <int, int> a[N + 1];
///a[i].first = giá trị
///a[i].second = vị trí ban đầu

void read(){
    cin >> n >> x;
    for(int i = 1; i <= n; ++i){
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a + 1, a + n + 1);
}

void solve(){
    int i = 1, j = n;
    while(i < j){
        if(a[i].first + a[j].first == x){
            cout << a[i].second << " " << a[j].second;
            return;
        }
        else if(a[i].first + a[j].first > x) --j;
        else if(a[i].first + a[j].first < x) ++i;
    }
    cout << "IMPOSSIBLE";
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    read();
    solve();

    return 0;
}