---
title
Hai con trỏ (Two pointers)
---

Hai con trỏ (Two pointers)
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

# Lời mở đầu
- Bài viết giới thiệu **kĩ thuật hai con trỏ** cùng với các bài tập vận dụng cơ bản.
- Đây là một kĩ thuật xuất hiện nhiều trong lập trình, dùng để tối ưu thời gian và không gian xử lí của chương trình.
*(Lưu ý: Tránh nhầm lẫn **kĩ thuật hai con trỏ** với **con trỏ trong C++**).*
- Đây là một **kĩ thuật** dùng để **tối ưu**, không phải **thuật toán** nên ta có thể áp dụng trong nhiều dạng bài.
- Ta có thể áp dụng kĩ thuật này trong nhiều bài khác nhau, trong bài viết này mình sẽ liệt kê một số dạng bài thông dụng nhất của **hai con trỏ** và một số bài toán liên quan để dễ hình dung nhất.

# Hai con trỏ cùng chiều

## Định nghĩa

- **Hai con trỏ** là kĩ thuật sử dụng hai con trỏ chạy **song song** với nhau trong 1 vòng lặp để duyệt qua các phần tử trong mảng **cùng theo 1 chiều** nhất định.
- Chính việc chạy **song song** thay vì chạy lồng nhau như cách duyệt thông thường giúp ta tối ưu được độ phức tạp thời gian của bài toán.
- Điều kiện để sử dụng kĩ thuật này là mảng phải có tính chất của hàm nhất biến. Ví dụ: Mảng $a$ được sắp xếp tăng dần, phần tử ở vị trí càng lớn thì có giá trị càng lớn (hoặc giảm dần, phần tử ở vị trí càng lớn thì có giá trị càng nhỏ).

## Bài toán 1: Gộp mảng

### Đề bài
- Cho hai dãy số **đã được sắp xếp không giảm** $a$ và $b$. Mảng $a$ có độ dài $n$, mảng $b$ có độ dài $m$.
- **Yêu cầu:** In ra mảng $c$ **không giảm** có độ dài $n+m$. Trong đó, mảng $c$ bao gồm tất cả phần tử của 2 mảng $a, b$.

#### Input
- Dòng đầu gồm hai số nguyên dương $n, m$.
- Dòng thứ hai bao gồm $n$ số nguyên $a_i$ là phần tử của mảng $a$.
- Dòng thứ ba bao gồm $m$ số nguyên $b_j$ là phần tử của mảng $b$.

#### Output
- Gồm 1 dòng duy nhất có $n+m$ số nguyên $c_i$ là phần tử của mảng $c$.

#### Giới hạn
- $2 \le n + m \le 3 \cdot 10^6$
- $-10^9 \le a_i, b_j \le 10^9$

#### Sample Input

6 7
1 6 9 13 18 18
2 3 8 13 15 21 25

#### Sample Output

1 2 3 6 8 9 13 13 15 18 18 21 25 

### Lời giải
:::spoiler **Ý tưởng**
- Vì giới hạn lớn nên ta không thể nhập hết $n+m$ số và sắp xếp lại.
- Mảng $a, b$ đều được **sắp xếp không giảm**, mảng $c$ sẽ gồm những phần tử của hai mảng trên theo chiều tịnh tiến từ $a_1 \rightarrow a_n$ và từ $b_1 \rightarrow b_m$. Chúng ta có thể sử dụng kĩ thuật **hai con trỏ**.
- Gọi $i,j$ lần lượt là con trỏ ở duyệt trên mảng $a,b$. Mảng $c$ được sắp xếp không giảm, ta kiểm tra $a_i,b_j$ và thêm vào mảng $c$ hiện tại phần tử nhỏ hơn. Sau đó ta tăng giá trị biến con trỏ cho đến khi mảng $c$ đủ $n+m$ phần tử.
:::

:::spoiler **Cài đặt**

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    int a[n + 1], b[m + 1], c[n + m + 1];

    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int j = 1; j <= m; j++) cin >> b[j];

    int cnt = 1; //cnt lưu chỉ số của mảng c
    for (int i = 1, j = 1; cnt <= n + m; cnt++)
    {
        if (j > m || (i <= n && a[i] < b[j]))
        {
            c[cnt] = a[i]; 
            i++; 
        // nếu mảng b đã thêm hết phần tử hoặc a[i] < b[j] thì thêm a[i] vào mảng c
        }
        else
        {
            c[cnt] = b[j];
            j++; 
        //nếu không thì thêm phần tử b[j] vào mảng c
        }
    }

    for (int i = 1; i <= n + m; i++) cout << c[i] << ' ';
    return 0;
}

#### Độ phức tạp thời gian
- Vì duyệt tăng dần từ đầu đến cuối mảng, con trỏ $i$ tăng không quá $n$ lần và con trỏ $j$ tăng không quá $m$ lần. Độ phức tạp thời gian của bài toán là $O(n+m)$.
:::

# Hai con trỏ ngược chiều

## Định nghĩa
- Như hai con trỏ **cùng chiều**, hai con trỏ **ngược chiều** sử dụng hai con trỏ cùng một lúc trong vòng lặp để duyệt qua các phần tử của mảng.
- Điểm khác biệt ở hai con trỏ **cùng chiều** và **ngược chiều** là cách chúng ta duyệt và thay đổi giá trị hai biến con trỏ.
- Ở hai con trỏ **ngược chiều**, ta duy trì hai biến con trỏ lần lượt ở *đầu* và *cuối* mảng. Sau khi xử lí, ta sẽ **tăng** giá trị biến con trỏ ở vị trí *đầu* hoặc **giảm** giá trị biến con trỏ ở vị trí *cuối* cho đến khi thỏa mãn một điều kiện nào đó (ví dụ như khi giá trị hai con trỏ bằng nhau).
- Chính vì chiều thay đổi giá trị của hai con trỏ không giống nhau (một con trỏ **tăng** giá trị và một con trỏ **giảm** giá trị qua các lần lặp) nên kĩ thuật này được gọi là hai con trỏ **ngược chiều**.

## Bài toán 2: Tìm cặp số
### Đề bài
- Cho một mảng số nguyên $a$ có $n$ phần tử được sắp xếp theo thứ tự **tăng dần**.
- Hãy tìm hai vị trí $i, j$ khác nhau bất kỳ sao cho tổng của hai phần tử ở hai vị trí đó có giá trị là $x$. Nếu không có cặp số nào thỏa mãn thì in ra `-1`.

#### Input
- Dòng đầu gồm hai số nguyên dương $n, x$.
- Dòng thứ hai gồm $n$ số nguyên dương $a_i$ là phần tử của mảng $a$ đã được sắp xếp **tăng dần**.
- Đầu vào đảm bảo tồn tại **nhiều nhất 1 cặp số** thỏa mãn.

#### Output
- Gồm 1 dòng duy nhất in cặp chỉ số $i, j$ khác nhau sao cho $a_i+a_j=x$ hoặc `-1` nếu không có đáp án nào thỏa mãn.

#### Giới hạn
- $1 \le n\le 3 \cdot 10^6$
- $1 \le x, a_i \le 10^9$

#### Sample Input

7 16
2 5 6 8 10 12 15

#### Sample Output

3 5

### Lời giải
:::spoiler **Ý tưởng**
- Ta có thể duyệt trâu bài này bằng cách xét từng cặp chỉ số $i, j$ và so sánh tổng của cặp số đó với giá trị $x$, tuy nhiên cách làm này có độ phức tạp là $O(n^2)$, không phù hợp với giới hạn bài toán. Vì thế ta cần tìm một giải pháp tối ưu hơn, bài viết này sẽ hướng dẫn cách áp dụng **kĩ thuật hai con trỏ ngược chiều** vào bài toán trên.
- Giả sử ban đầu ta đặt hai biến con trỏ $i, j$ lần lượt ở *đầu* và *cuối* mảng, ta bắt đầu so sánh từng cặp giá trị $a_i+a_j$ với giá trị $x$. Tổng cộng sẽ có ba trường hợp sau:
1. $a_i+a_j=x$: Cặp chỉ số $i, j$ thỏa mãn điều kiện đề bài, lúc này ta chỉ cần in ra hai chỉ số $i, j$ và kết thúc bài toán.
2. $a_i+a_j>x$: Tổng của hai phần tử $a_i, a_j$ lớn hơn giá trị $x$ cần tìm, ta cần tìm một cặp chỉ số khác có tổng nhỏ hơn $a_i+a_j$ lúc này. Ta có thể thấy mảng $a$ đã được sắp xếp tăng dần, tức là $a_i < a_{i+1}$ với mọi $i$ từ $1 \rightarrow n-1$, cần phải giảm giá trị biến con trỏ $j$ xuống vì lúc này phần tử $a_{j-1}$ sẽ bé hơn phần tử $a_j$, từ đó giảm được tổng giá trị $a_i+a_j$, giúp ta tiếp cận gần với đáp án hơn.
3. $a_i+a_j<x$: Tổng của hai phần tử $a_i, a_j$ bé hơn giá trị $x$ cần tìm, lúc này áp dụng tư tưởng tương tự như ở trường hợp 2, ta sẽ tăng giá trị của con trỏ $i$ lên $i+1$ để tiếp tục tìm kiếm.
- Để dễ hiểu hơn, bạn có thể xem qua gif minh họa dưới đây:
:::

:::spoiler **Cài đặt**

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n, x;
    cin >> n >> x;

    int a[n + 1];
    for (int i = 1; i <= n; i++) cin >> a[i];

    int i = 1, j = n; //i và j lần lượt là hai con trỏ ở hai đầu của mảng a
    bool found = 0; //biến found cho biết đáp án đã được tìm thấy hay chưa
    while (i < j && found == 0) //lặp để tìm đáp án nếu đáp án chưa tìm được và i < j
    {
        if (a[i] + a[j] == x) //trường hợp 1
        {
            cout << i << ' ' << j;
            found = 1;
        } 
        else
        if (a[i] + a[j] > x) j--; //trường hợp 2
        else i++; //trường hợp còn lại (trường hợp 3)
    }

    if (found == 0) cout << -1; //nếu đáp án vẫn chưa được tìm thấy thì in -1
    return 0;
}

#### Độ phức tạp thời gian
- Vì ta chỉ lặp cho đến khi tìm được đáp án hoặc khi $i = j$, trường hợp tệ nhất ta chỉ mất $n$ lần lặp, vì vậy độ phức tạp sẽ là $O(n)$.
:::

# Dạng bài kiểm tra trên đoạn liên tiếp

## Định nghĩa
- Có một số bài toán yêu cầu liên quan đến đoạn liên tiếp trong mảng như *đếm số đoạn con, tìm đoạn dài nhất*. Bài tập dạng này thường có nhiều cách giải, một trong những bài thuộc dạng này có thể giải bằng **kĩ thuật hai con trỏ**.
*(**Ví dụ**: Đếm đoạn có tổng không vượt quá một giá trị, tìm đoạn dài nhất có ước chung lớn nhất của cả đoạn là 1)*
- Áp dụng **kĩ thuật hai con trỏ** cùng chiều, ta có thể kiểm tra một đoạn liên tiếp nếu đoạn đó có **tính chất của hàm nhất biến**. Nói một cách đơn giản, tính chất của đoạn liên tiếp không thay đổi khi ta so sánh nó với một đoạn khác có chung ít nhất 1 biên.
*(**Ví dụ**: Đoạn càng dài thì tổng của đoạn càng lớn, Đoạn càng dài thì số lượng phần tử phân biệt càng lớn)*
- Để dễ hiểu hơn, ta có thể xem đoạn code [dưới đây](#Cách-giải-chung).

## Cách giải chung
- Có nhiều cách để cài đặt dạng này. Một trong những cách có thể tham khảo để cài đặt được đa số bài tập ở dạng này được trình bày qua đoạn pseudo-code dưới đây

for (int l = 1, r = 1; r <= n; r++)
{
    //Thêm phần tử r;
    while (/*Đoạn không thỏa điều kiện*/)
    {
        //Xóa phần tử l;
        //tăng l;
    }
    //Truy vấn kết quả
}

## Bài toán 3: Đoạn đẹp dài nhất
### Đề bài
- Cho dãy số $a$ gồm $n$ phần tử nguyên dương. Một đoạn $a_{l..r}$ được gọi là **đẹp** nếu tổng của nó không vượt quá $s$
- **Yêu cầu:** tìm ra **độ dài của đoạn đẹp dài nhất** trong mảng $a$.

#### Input
- Dòng đầu gồm hai số nguyên dương $n, s$.
- Dòng thứ hai bao gồm $n$ số nguyên $a_i$ là phần tử của mảng $a$.

#### Output
- Gồm 1 số nguyên duy nhất là kết quả của bài toán

#### Giới hạn
- $2 \le n \le 3 \cdot 10^6$
- $1 \le s \le 10^{18}$
- $1 \le a_i\le 10^9$

#### Sample Input

7 20
2 6 4 3 6 8 9

#### Sample Output

4

- Giải thích: đoạn tìm được là $a_{1..4}$. $2+6+4+3=15 \le 20$

### Lời giải
:::spoiler **Ý tưởng**
- Nhận thấy mảng $a$ là **nguyên dương**, ta có thể biết rằng **đoạn càng dài thì tổng càng lớn**
- Với từng giá trị $r (1 \le r \le n)$, ta cần tìm giá trị $l$ nhỏ nhất sao cho $l \le r$ và tổng trong đoạn $a_{l..r} \le s$
- Để thực hiện hóa điều đó, ta gọi biến $sum$ là tổng đang xét. Duyệt qua mảng, ở mỗi lần duyệt ta cộng $a_r$ vào $sum$. Nếu tổng vượt quá $s$ thì ta xóa $a_l$ khỏi $sum$ và tăng giá trị $l$ lên cho đến khi $sum < s$
- Kết quả của bài toán là $max(r-l+1)$ với mỗi $1 \le r \le n$
:::

:::spoiler **Cài đặt**

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, ans = 0;
    long long s;
    cin >> n >> s;
    int a[n + 1];
    for (int i = 1; i <= n; i++) cin >> a[i];

    long long sum = 0;
    for (int l = 1, r = 1; r <= n; r++)
    {
        sum += a[r];
        while (sum > s)
        {
            sum -= a[l];
            l++;
        }
        ans = max(ans, r - l + 1);
    }
    
    cout << ans;
    return 0;
}

### Độ phức tạp thời gian
- Duyệt bằng 1 vòng lặp và chạy song song 2 biến đếm, độ phức tạp là $O(n)$.
:::

# Các lỗi thường gặp khi cài đặt

## Lỗi lặp vô hạn
- Lỗi này thường xảy ra khi điều kiện của vòng lặp `while` (hoặc cả `for` trong C++) bị sai hoặc con trỏ không được thay đổi giá trị. Dẫn tới chương trình không bao giờ kết thúc hoặc gặp lỗi **Segmentation Fault**.

### Code ví dụ về lỗi: [Gộp mảng](#Bài-toán-1-Gộp-mảng)

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    int a[n + 1], b[m + 1], c[n + m + 1];

    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int j = 1; j <= m; j++) cin >> b[j];

    int cnt = 1; //cnt lưu chỉ số của mảng c
    for (int i = 1, j = 1; i + j <= n + m; cnt++)
    {
        if (j > m || (i <= n && a[i] < b[j])) c[cnt] = a[i];
        else c[cnt] = b[j];
    }

    for (int i = 1; i <= n + m; i++) cout << c[i] << ' ';
    return 0;
}

### Vấn đề
- Chương trình gặp lỗi **Segmentation Fault**.
- Trong chương trình trên, lỗi Segmentation Fault phát sinh khi biến `cnt` vượt quá kích thước mảng $c$ cho phép.

### Nguyên nhân
- Do vị trí của con trỏ $i, j$ không bao giờ được cập nhật nên điều kiện $i + j \le m + n$ luôn đúng. Dẫn tới vòng lặp lặp lại tới khi biến `cnt` được tăng dần mỗi lần lặp vượt quá kích thước mảng $c$ và gây ra **Segmentation Fault**.

### Cách khắc phục
- Kiểm tra kỹ điều kiện của vòng lặp và vị trí của các con trỏ có được thay đổi sau mỗi lần lặp hay không.
- Code mẫu: [Lời giải bài toán 1](#Lời-giải).

## Lỗi truy cập giá trị ở bên ngoài mảng
<!-- Truy cập phần tử thử n+1 trở lên khi mảng chỉ khai báo n phần tử -->
- Lỗi này thường xảy ra do sai điều kiện so sánh vị trí con trỏ với kích thước mảng. Có khả năng cao làm ảnh hưởng tới kết quả bài toán, và có thể gây ra **Runtime Error** làm "chết" chương trình.

### Code ví dụ về lỗi: [Bộ số tam giác](#Bài-toán-2-Bộ-số-tam-giác)

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    long long ans = 0;
    cin >> n;
    
    int a[n + 1];
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    
    for (int i = 1; i <= n; i++)
    {
        int k = i + 1; // Biến k và j chạy song song với nhau
        for (int j = i + 1; j <= n; j++)
        {
            while (k <= n && a[k + 1] < a[i] + a[j]) k++; // Sử dụng Bất đẳng thức trong tam giác để kiểm tra xem 3 cạnh có thể tạo thành tam giác hay không
            ans += k - j;
        }
    }
    
    cout << ans;
    return 0;
}

### Vấn đề
- Đoạn code trên sẽ lỗi **Segmentation Fault** (truy cập vùng nhớ không được hệ điều hành cấp cho chương trình) hoặc **Wrong Answer** (Kết quả sai) ở một số trường hợp.
- Trong chương trình trên, vấn đề phát sinh từ con trỏ $i$ hoặc $j$ có thể nằm ngoài kích thước mảng là $n$ và $m$ dẫn tới truy cập vùng nhớ không được cấp phép, sinh ra lỗi Segmentation Fault.

### Nguyên nhân
- Ở câu lệnh while dòng `20` của đoạn code trên, ta thấy nếu $k \le n$ thì sẽ so sánh $a_{k+1}$ có bé hơn $a_i+a_j$ hay không. Nếu như $k=n$ sẽ tiếp tục so sánh phần tử $a_{k+1}$ (tức $a_{n+1}$) nhưng ta khai báo mảng $a$ chỉ có $n+1$ phần tử, từ đó chỉ truy cập được tối đa đến phần tử $a_n$ tức $a_k$ (do $k=n$). Khi đó nếu ta truy cập giá trị phần tử $a_{n+1}$, giá trị truy cập được ở con trỏ là giá trị rác, hoặc chương trình sẽ trả về lỗi **Segmentation Fault**.

### Cách khắc phục
- Kiểm tra kỹ các điều kiện so sánh vị trí con trỏ với kích thước mảng.
- Một cách khác để xử lí lỗi này là **giới hạn biên** của mảng. Trước hết ta cần khai báo mảng $a,b$ dư ít nhất 1 phần tử, sau đó, ta đặt $a_{n+1}$ và $b_{m+1}$ là $x$, với $x \ge max(a_n,b_m)$. Nhờ đó, điều kiện $a[i] < b[j]$ sẽ không bao giờ thõa nếu con trỏ $i > n$, hoặc luôn thõa nếu $j > m$.
*(**Lưu ý:** Nên đặt giá trị $x$ lớn hơn giới hạn đề bài đưa ra, nhiều trường hợp có thể đặt là hằng số `LLONG_MAX` hoặc `INT_MAX` có sẵn trong C++)*
- Code mẫu: [Lời giải bài toán 2](#Lời-giải1).

# Bài tập

## Bài 1: [Bộ số tam giác](https://lqdoj.edu.vn/problem/1819bosotg)

### Đề bài
- Cho dãy số $a$ gồm $n$ phần tử nguyên dương $a_1,a_2,...,a_n$. Một bộ ba số được gọi là bộ số tam giác, nếu ba số này tạo thành ba cạnh của một tam giác nào đó.
- **Yêu cầu**: Hãy đếm xem trong dãy $a$ có bao nhiêu bộ số tam giác $(a_i,a_j,a_k)$ với $i,j,k$ đôi một khác nhau.

#### Input
- Dòng đầu là số $n$ - số lượng phần tử của dãy $a$.
- Dòng tiếp theo là $n$ phần tử của dãy $a$, mỗi phần tử cách nhau một dấu cách.

#### Output
- Ghi một số nguyên duy nhất là số lượng bộ số tam giác hợp lệ.

#### Giới hạn
- $1 \le n \le 5000$
- $1 \le a_i \le 10^9$

#### Sample Input

5
4 3 1 5 7 

#### Sample Output

3

### Lời giải
:::spoiler **Ý tưởng**
- Ta có thể nghĩ ra thuật toán ngây thơ duyệt qua tất cả bộ số bằng 3 vòng lặp. Tuy nhiên, vì $n \le 5000$ là quá lớn cho cách duyệt 3 vòng lặp nên ta phải nghĩ cách để tối ưu.
- Giả sử các phần tử trong mảng **được sắp xếp không giảm**, khi ta duyệt từng cặp số, ta không cần tìm số thứ ba để ghép từng bộ số mà có thể tìm ra **vị trí lớn nhất** có thể tạo thành tam giác với cặp số đang xét.
- Duyệt qua từng cặp số $(i,j)$ khác nhau, gọi **vị trí lớn nhất** ta tìm được là $k$. Ta có thể ghép $(a_i,a_j,a_{j+1}),(a_i,a_j,a_{j+2}),...,(a_i,a_j,a_{k})$. Do đó, số tam giác có thể ghép là $k-j$. Để kiểm tra, ta có thể sử dụng [Bất đẳng thức tam giác](https://vi.wikipedia.org/wiki/B%E1%BA%A5t_%C4%91%E1%BA%B3ng_th%E1%BB%A9c_tam_gi%C3%A1c).
- Để tìm được vị trí đó, ta có thể sử dụng **kĩ thuật hai con trỏ** hoặc **tìm kiếm nhị phân**. Tuy nhiên, **tìm kiếm nhị phân** không nằm trong phạm vi bài viết. Vì vậy, bài viết này sẽ hướng dẫn cách giải sử dụng **kĩ thuật hai con trỏ**.
:::

:::spoiler **Cài đặt**

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    long long ans = 0;
    cin >> n;
    
    int a[n + 2];
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    a[n + 1] = INT_MAX; // Để dễ cài đặt thì ta đặt a[n + 1] là phần tử lớn hơn tất cả giá trị a[i] + a[j]
    
    for (int i = 1; i <= n; i++)
    {
        int k = i + 1; // Biến k và j chạy song song với nhau
        for (int j = i + 1; j <= n; j++)
        {
            while (k + 1 <= n && a[k + 1] < a[i] + a[j]) k++; // Sử dụng Bất đẳng thức trong tam giác để kiểm tra xem 3 cạnh có thể tạo thành tam giác hay không
            ans += k - j;
        }
    }
    
    cout << ans;
    return 0;
}

#### Độ phức tạp thời gian
- Ta duyệt qua từng cặp số và sử dụng kĩ thuật **hai con trỏ** thay vì kiểm tra từng bộ ba số, độ phức tạp của bài toán là $O(n^2)$.
:::

## Bài 2: [Ferris Wheel](https://cses.fi/problemset/task/1090/)

### Đề bài
- Có $n$ người muốn chơi đu quay, nhiệm vụ phân bổ cabin cho mỗi người sao cho số cabin cần dùng là ít nhất.
- Mỗi cabin có thể chứa từ 1 đến 2 người, tổng cân nặng trong một cabin không được vượt quá $x$. Cân nặng của mỗi người được cho biết trước.
- **Yêu cầu**: Tìm số lượng cabin **ít nhất** cần bố trí cho **tất cả** $n$ người.

#### Input
- Dòng đầu gồm hai số nguyên dương $n, x$ cho biết số lượng người và cân nặng tối đa được cho phép trong mỗi cabin.
- Dòng thứ hai bao gồm $n$ số nguyên $p_i, p_{i+1},...p_n$ là cân nặng của từng người.

#### Output
- Gồm 1 số nguyên là số lượng cabin **ít nhất** cần bố trí cho **tất cả** $n$ người.

#### Giới hạn
- $1 \le n \le 2 \cdot 10^5$
- $1 \le x \le 10^9$
- $1 \le p_i \le x$

#### Sample Input

4 10
7 2 3 9

#### Sample Output

3

### Lời giải
:::spoiler **Ý tưởng**
<!-- SẼ BỔ SUNG SAU -->
- Đầu tiên, ta có thể bố trí $n$ cabin cho cả $n$ người, nhưng như thế chưa phải là đáp án ít nhất, vì thế sẽ có một số cabin chứa hai người để giảm thiểu số lượng cabin.
- Ta sẽ cố gắng ghép người có cân nặng lớn nhất với người có cân nặng bé nhất (tư tưởng tham lam), để quá trình tìm người có cân nặng lớn nhất và bé nhất diễn ra một cách thuận lợi, ta sẽ sắp xếp lại mảng cân nặng từng người theo thứ tự **không giảm**.
- Sau khi sắp xếp lại mảng, ta sẽ bắt đầu quá trình ghép cabin. Đặt con trỏ $i, j$ lần lượt ở vị trí *đầu* và *cuối* mảng là vị trí của người có cân nặng bé nhất và vị trí của người có cân nặng lớn nhất **chưa được ghép cặp cabin với người khác**. Nếu ta có thể ghép $(a_i,a_j)$, hay nói cách khác: $a_i+a_j\le x$, ta sẽ ghép cho người thứ $i$ và người thứ $j$ chung cabin.
- Lúc này, ta tăng $i$ và giảm $j$ vì ta đã xử lí xong cặp chỉ số $(i, j)$, sau đó giảm kết quả 1 đơn vị (do ta giảm từ 2 cabin xuống còn 1 cabin). Nếu không thì giảm $j$ do $j$ không thể ghép chung cabin với người khác nữa, vì $i$ là `vị trí của người có cân nặng bé nhất chưa được ghép cặp cabin với người khác` nên lúc này $a_i+a_j$ đã đạt giá trị bé nhất, nếu $a_i+a_j > x$ thì không còn phần tử nào có vị trí $k>i$ có thể ghép cặp cabin với $a_j$ nữa (do mảng $a$ đã được sắp xếp theo thứ tự **không giảm** nên $a_k+a_j>x$).
- Sau đó ta tiếp tục lặp lại các bước trên cho đến khi xử lí xong $n$ người $(i \ge j)$.
:::

:::spoiler **Cài đặt**

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{    
    int n, x;
    cin >> n >> x;

    int ans = n, a[n + 1];
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
 
    int i = 1, j = n;
    while (i < j)
    {
        if (a[i] + a[j] <= x)
        {
            i++;
            j--;
            ans--;
        } else j--;
    }
    
    cout << ans;
    return 0;
}

#### Độ phức tạp thời gian
- Tương tự, ta chỉ duyệt cho đến khi $i \ge j$ thì dừng, con trỏ được cập nhật tối đa $n-1$ lần (trong trường hợp kết quả bài toán đúng bằng $n$), vì vậy độ phức tạp cuối cùng của bài toán cũng là $O(n)$.
:::

## Bài 3: Đếm đoạn đẹp dài nhất
### Đề bài
- Cho dãy số $a$ gồm $n$ phần tử nguyên dương. Một đoạn $a_{l..r}$ được gọi là **đẹp** nếu tổng của nó không vượt quá $s$
- **Yêu cầu:** đếm số lượng **đoạn đẹp dài nhất** trong mảng $a$.

#### Input
- Dòng đầu gồm hai số nguyên dương $n, s$.
- Dòng thứ hai bao gồm $n$ số nguyên $a_i$ là phần tử của mảng $a$.

#### Output
- Gồm 1 số nguyên duy nhất là kết quả của bài toán

#### Giới hạn
- $2 \le n \le 3 \cdot 10^6$
- $1 \le s \le 10^{18}$
- $1 \le a_i\le 10^9$

#### Sample Input

7 20
2 6 4 3 6 8 9

#### Sample Output

19

### Lời giải
:::spoiler **Ý tưởng**
- Ta có thể thấy mảng có tính chất như [Bài toán 5](#Bài-toán-5:-Đoạn-đẹp-dài-nhất).
- Để đếm được số đoạn đẹp, ta có thể dùng ý tưởng như đếm tam giác từ [Bài toán 2](#Bài-toán-2:-Bộ-số-tam-giác), nếu ta chọn phần tử kết thúc là $r$ tìm được $l$ vẫn thỏa đề xa nhất về bên trái, tất cả các đoạn khi ta chọn phần tử đầu nằm trong $[l..r]$ đều thõa yêu cầu bài toán.
- Vậy nên kết quả bài toán là: $\sum_{r=1}^{n} r-l+1$, với $l,r$ đã được nêu ở trên
:::

:::spoiler **Cài đặt**

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    long long s, ans = 0;
    cin >> n >> s;
    int a[n + 1];
    for (int i = 1; i <= n; i++) cin >> a[i];

    long long sum = 0;
    for (int l = 1, r = 1; r <= n; r++)
    {
        sum += a[r]; // thêm a[r] vào đoạn đang xét
        while (sum > s)
        {
            sum -= a[l]; // xóa a[l] khỏi đoạn nếu tổng vượt quá s
            l++;
        }
        ans += r - l + 1;
    }
    
    cout << ans;
    return 0;
}

### Độ phức tạp thời gian
- Tương tự như [Bài toán 3](#Bài-toán-3:-Đoạn-đẹp-dài-nhất), độ phức tạp của bài toán là $O(n)$.
:::

# Bài tập vận dụng

- Do đây là một chủ đề quan trọng, ngoài các bài tập trên, 2SG còn có một số bài tập bổ sung để các bạn có thể tự thử sức mình.
- [CSES - Sum of Two Values](https://cses.fi/problemset/task/1640)
- [Tuyển sinh 10 Phổ Thông Năng Khiếu 2023 - Marble](https://gdoj.eu.org/problem/ptnk_marble)
- [CSES - Sum of Three Values](https://cses.fi/problemset/task/1641)
- [VNOJ - Khai bút đầu xuân](https://oj.vnoi.info/problem/sopenp)

# Nguồn tham khảo
- [VNOI Wiki - Kĩ thuật hai con trỏ](https://vnoi.info/wiki/algo/basic/two-pointers.md)
- [Codeforces EDU - ITMO Academy: pilot course](https://codeforces.com/edu/courses)