MỤC LỤC
Phần I ..................................................................................................................................... 2
MỞ ĐẦU................................................................................................................................ 2
1. Mục đích của sáng kiến .................................................................................................. 2
2. Tính mới và ưu điểm nổi bật .......................................................................................... 2
3. Đóng góp của sáng kiến ................................................................................................. 2
Phần II .................................................................................................................................... 3
NỘI DUNG ............................................................................................................................ 3
1. Kỹ thuật Two Pointer là gì? ........................................................................................... 3
2. Tại sao sử dụng kỹ thuật Two Pointer? ......................................................................... 3
3. Làm thế nào để sử dụng kỹ thuật Two Pointer? ............................................................ 3
3.1. Ví dụ 1: .................................................................................................................... 3
3.2. Ví dụ 2 ...................................................................................................................... 9
3.3. Ví dụ 3 .................................................................................................................... 12
3.4. Ví dụ 4 .................................................................................................................... 16
3.5. Ví dụ 5 .................................................................................................................... 18
4. Bài tập ứng dụng .......................................................................................................... 21
4.1. Bài 1 ....................................................................................................................... 24
4.2. Bài 2 ....................................................................................................................... 24
4.3. Bài 3 ....................................................................................................................... 27
4.4. Bài 4 ....................................................................................................................... 29
4.5. Bài 5: ...................................................................................................................... 32
5. Bài tập luyện tập ........................................................................................................... 34
5.1. Mật mã ................................................................................................................... 34
5.2. Cellular Network .................................................................................................... 35
5.3. Tập xe ..................................................................................................................... 38
5.4. Dãy số..................................................................................................................... 40
5.5. Xếp thùng ............................................................................................................... 41
5.6. Chia giày ................................................................................................................ 41
5.7. WEDDING............................................................................................................. 42
Phần III: KẾT LUẬN .......................................................................................................... 44

TÀI LIỆU THAM KHẢO………………………………………………………………..44
1


Phần I: MỞ ĐẦU
1. Mục đích của sáng kiến
Trong Tin học, khi lập trình một bài tốn thì vấn đề đặt ra cho mỗi người lập trình
khơng phải chỉ là cho ra đáp số đúng, mà vấn đề quan trọng hơn là phải đưa ra đáp số đúng
trong thời gian ngắn nhất. Thông thường, để đạt được độ phức tạp thuật tốn như mong
muốn, cách làm thường là tìm ra một thuật toán ban đầu làm cơ sở, rồi từ đó dùng các kỹ
năng để giảm độ phức tạp của thuật toán. Kỹ thuật hai con trỏ là một chuyên đề rất quan
trọng và áp dụng rất nhiều vào các bài tốn. Trong chun đề này sẽ giúp bạn tìm hiểu thêm
về kỹ thuật hai con trỏ. Kỹ thuật này được sử dụng khá phổ biến, giúp chương trình tiết
kiệm thời gian và khơng gian xử lý.
Qua q trình giảng dạy, học tập, tìm tịi, tơi chọn lọc và tích lũy được một số kinh
nghiệm về thuật toán hai con trỏ. Do đó, tơi viết lựa chọn viết chun đề : “Vận dụng Kỹ
thuật hai con trỏ để giải một số bài tập Tin học”. Đây cũng là một tài liệu giúp các em học
sinh giải quyết các bài tập tin học.

2. Tính mới và ưu điểm nổi bật
Khi giải quyết bài toán chúng ta thường hay sử dụng 2 vòng lặp for. Tuy đã đạt được
kết quả nhất định nhưng khơng giải quyết được trọn vẹn bài tốn khi dữ liệu lớn. Sử dụng
kỹ thuật hai con trỏ có thể giải quyết tốt hơn trong nhiều bài toán.
Sáng kiến được áp dụng vào giảng dạy chuyên đề ở lớp chun tin và đã có những
thành cơng nhất định.
Ưu điểm của sáng kiến: Code ngắn gọn, dễ hiểu.

3. Đóng góp của sáng kiến
Nguồn tài liệu cần thiết cho thầy cô và các em học sinh lớp chuyên tin trong Trường
và giáo viên các trường THPT khác tham khảo.

Xuất phát từ yêu cầu giảng dạy chuyên đề cho các lớp chuyên Tin nên Tôi tổng hợp
các bài tập lại thành chuyên đề đó là: “Vận dụng Kỹ thuật hai con trỏ để giải một số bài
tập Tin học”.

2


Phần II: NỘI DUNG
1. Kỹ thuật Two Pointer là gì?
Với Two Pointer 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ể:
•

Opposite-Directional: mỗi con trỏ được đặt ở hai đầu của mảng và chúng di chuyển về
phía nhau cho đến khi chúng gặp nhau hoặc thỏa mãn một số điều kiện.

•

Equi-Directional: mỗi con trỏ đều bắt đầu ở đầu mảng, một con là con trỏ di chuyển
chậm trong khi con còn lại là con trỏ nhanh hơn, 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 đó.

2. Tại sao sử dụng kỹ thuật Two Pointer?
Lý do quan trọng nhất đằng sau việc sử dụng kỹ thuật này là để giảm độ phức
tạp về thời gian của một bài toán từ O(n3) hoặc O(n2) thành O(n) hoặc O(nlogn) tùy
thuộc vào việc mảng có được sắp xếp hay khơng.

3. Làm thế nào để sử dụng kỹ thuật Two Pointer?
Chúng ta sẽ tìm hiểu kỹ thuật này bằng cách xem qua ví dụ sau:

3.1. Ví dụ 1: Trộn dãy
Tên file MERGER.*
Nhập vào hai dãy số nguyên dương đã sắp xếp theo thứ tự khơng giảm
•

𝐴 = (𝑎1 ≤ 𝑎2 ≤ ⋯ ≤ 𝑎𝑚 )

•

𝐵 = (𝑏1 ≤ 𝑏2 ≤ ⋯ ≤ 𝑏𝑛 )

•

𝑚, 𝑛 ≤ 105

•

𝑎𝑖 , 𝑏𝑖 ≤ 109

Yêu cầu: Hãy xây dựng dãy 𝐶 gồm tất cả các phần tử trong dãy 𝐴 và dãy 𝐵 xếp theo thứ tự
tăng dần.
Dữ liệu vào:
•

Dịng đầu là hai số m và n

•

Dịng tiếp theo là m số: là dãy 𝑎1 , 𝑎2 , … . , 𝑎𝑚


•

Dịng tiếp theo là n số: là dãy 𝑏1 , 𝑏2 , … . , 𝑏𝑛
3


Kết quả ra:
•

Gồm n + m số được sắp thành dãy tăng dần

Ví dụ:
Input

Output

54

123456789

13579
2468

3.1.1. Hướng dẫn giải thuật
Cách 1: Cách đơn giản nhất, ta sẽ đọc đồng thời cả hai dãy và vào cùng một mảng sau
đó dùng hàm sort để thu được kết quả.
#include<bits/stdc++.h>
using namespace std;
const int MaxN = 1 + 1e5;
int n, m, c[MaxN];

int main(){
cin >> n;
for(int i = 0 ; i < n ; ++i) cin >> c[i];
cin >> m;
for(int i = 0 ; i < m ; ++i) cin >> c[n + i];
sort(c, c + n + m);
for(int i = 0 ; i < n + m ; ++i) cout << c[i] << " ";
return 0;

4


}

Tuy nhiên, độ phức tạp của chương trình trên sẽ là O ((n+m)*log(n+m)) do ta
cần sort một mảng có kích thước n + m. Vậy liệu có cách làm nào tối ưu hơn không?
Cách 2: Cải tiến
Nhận xét:
Cho trước hai dãy số a và b được sắp xếp không giảm:
a=[1,3,6,8,10]
b=[2,6,7,12,14,15]
Làm cách nào để có thể ghép chúng thành một dãy số c cũng được sắp xếp không
giảm ?
Trước tiên, hãy cùng xác định phần tử đầu tiên của dãy c.
Vì dãy c được bố trí theo thứ tự khơng giảm, cho nên phần tử đầu tiên của dãy c phải
là phần tử có giá trị nhỏ nhất trong cả hai dãy a và b.
Ta có thể so sánh hai phần tử nhỏ nhất của hai dãy a, b và đưa phần tử có giá trị nhỏ
hơn vào vị trí đầu tiên của dãy c.
Dãy a và b đã được sắp xếp khơng giảm, vì thế hai phần tử nhỏ nhất ở đây chính là
hai phần tử ở vị trí đầu tiên ở mỗi dãy (a[1] và b[1]).

a=[1↓,3,6,8,10]
b=[2↓,6,7,12,14,15]
c=[1]
Bây giờ, phần tử tiếp theo của dãy c sẽ là phần tử nhỏ nhất trong các phần tử chưa
được đưa vào dãy c.
Dãy a và b đã được sắp xếp khơng giảm, vì thế sau khi đưa a[1] vào dãy c, a[2] là
phần tử nhỏ nhất chưa được chọn ở dãy a và b[1] là phần tử nhỏ nhất chưa được chọn ở
dãy b.
So sánh a[2] và b[1], chọn phần tử có giá trị nhỏ hơn và đưa vào dãy c.
a=[1,3↓,6,8,10]
b=[2↓,6,7,12,14,15]
5


c=[1,2]
Sau khi đưa b[1] vào dãy c, b[2] trở thành phần tử nhỏ nhất chưa được chọn ở dãy b.
Vẫn như thế, phần tử tiếp theo của dãy c sẽ là phần tử nhỏ nhất trong các phần tử
chưa được đưa vào dãy c.
So sánh b[2] và a[2], chọn phần tử có giá trị nhỏ hơn dãy và đưa vào dãy c.
a=[1,3↓,6,8,10]
b=[2,6↓,7,12,14,15]
c=[1,2,3]
Sau khi đưa a[2] vào dãy c, a[3] trở thành phần tử nhỏ nhất chưa được chọn ở dãy a.
Ta nhận thấy rằng:
•

Tại mọi thời điểm, phần tử tiếp theo được đưa vào dãy c sẽ là phần tử có giá trị nhỏ nhất

trong các phần tử chưa được chọn.
-


Bằng cách so sánh phần tử nhỏ nhất chưa được chọn ở dãy a và phần tử nhỏ nhất
chưa được chọn ở dãy b, phần tử nhỏ hơn sẽ được chọn vào dãy c.

•

•

Ban đầu, lúc dãy c chưa có phần tử nào
-

a[1] là phần tử nhỏ nhất chưa được chọn trong dãy a.

-

b[1] là phần tử nhỏ nhất chưa được chọn trong dãy b.

Khi đưa phần tử a[i] vào dãy c thì phần tử nhỏ nhất chưa được chọn trong dãy a sẽ

là a[i+1].
•

Khi đưa phần tử b[j] vào dãy c thì phần tử nhỏ nhất chưa được chọn trong dãy b sẽ

là b[j+1].
Thuật toán:
Dựa vào các nhận xét ở trên, ta có thể đưa ra cách làm như sau:
•

Ta có một con trỏ i ở mảng a thể hiện cho phần tử nhỏ nhất trong dãy a chưa được chọn


•

Ta có một con trỏ j ở mảng b thể hiện cho phần tử nhỏ nhất trong dãy b chưa được chọn

•

Ta sẽ lặp lại tiến trình sau cho đến khi tất cả phần tử hai dãy a và b được đưa vào dãy c

- Nếu như các phần tử của một trong hai dãy a và b đều được đưa vào dãy c (i = n hoăc j =
m) thì ta đưa tất cả các phần tử của dãy cịn lại vào
- Nếu khơng:
-

Xét hai phần tử ở vị trí i trong dãy a và j trong dãy b
6


▪

Chọn phần tử nhỏ hơn vào dãy c, nếu bằng nhau thì chọn bất kì

Tăng con trỏ của mảng có phần tử được đưa vào dãy c

3.1.2. Chương trình
#include<bits/stdc++.h>
using namespace std;
const int MaxN = 1 + 1e5;
int n, m, a[MaxN], b[MaxN];
vector<int> c;

int main(){
cin >> n;
for(int i = 0 ; i < n ; ++i) cin >> a[i];
cin >> m;
for(int i = 0 ; i < m ; ++i) cin >> b[i];
int i = 0, j = 0;
while(i < n && j < m){
if(i == n){
c.push_back(b[j]);
j++;
continue;
}
if(j == m){
c.push_back(a[i]);

7


i++;
continue;
}
if(a[i] < b[j]){
c.push_back(a[i]);
i++;
}
else {
c.push_back(b[j]);
j++;
}
}

for(int i : c) cout << i << " ";
return 0;
}

3.1.3. Độ phức tạp thuật tốn
Trong ví dụ trên ta sử dụng hai biến i và j như hai con trỏ trỏ đến hai phần tử nên kĩ
thuật này được gọi là Kỹ thuật hai con trỏ.
Vậy độ phức tạp của thuật toán trên là bao nhiêu? Ta thấy vòng lặp while lặp lại n +
m lần, mỗi thao tác trong vòng lặp là O(1) nên độ phức tạp của chương trình sẽ chỉ
là O(n+m).

8


3.2. Ví dụ 2
Capso.cpp
Cho dãy gồm n số nguyên, hãy tìm hai giá trị ở hai vị trí khác nhau mà có tổng là x?
Input:
• Dịng đầu ghi hai số ngun n, x
• Dịng thứ hai ghi n số ngun 𝑎1 , 𝑎2 , … , 𝑎𝑛
Output:
• In ra hai số nguyên là vị trí của hai giá trị thỏa mãn điều kiện. Nếu có nhiều hơn 1
đáp án, hãy ghi đáp án đúng bất kì, nếu khơng có đáp án, hãy in “IMPOSSIBLE”
Ràng buộc:
• 1 ≤ 𝑛 ≤ 2.105
• 1 ≤ 𝑥, 𝑎𝑖 ≤ 109
Ví dụ:
Input

Output


48

24

2751
7 16

35

2 5 6 8 10 12 15

3.2.1. Hướng dẫn giải thuật
Cách 1: Nếu làm theo cách bình thường sử dụng duyệt 2 vịng for, cách này chương
trình chạy chậm. Độ phức tạp thuật toán O(𝑛2 ).
for(int i=1; ifor(int j=i+1; j<=n; j++)
if(a[i]+a[j]==x)
{

9


cout << i <<" "<return 0;
}

Cách 2: Cải tiến sử dụng kỹ thuật hai con trỏ
Hãy cùng xem ví dụ sau đây.
Cho trước mảng số a được sắp xếp tăng dần và x=16:

a=[2,5,6,8,10,12,15]
Làm cách nào để có thể tìm hai vị trí khác nhau mà tổng hai phần tử ở hai vị trí đó có tổng
là x ?
Trước tiên, ta có một chút nhận xét sau:
•

a[1]
•

a[1]+a[7]=17>X⇒XCó thể thấy, tổng của a[7] với các phần tử khác trong dãy đều lớn hơn X. Vì thế ta

khơng quan tâm đến a[7] nữa.
a=[2,5,6,8,10,12,15]
a[1]+a[6]=14Có thể thấy, tổng của a[1] với các phần tử khác trong các phần tử ta quan tâm đều
nhỏ hơn x. Vì thế ta khơng quan tâm đến a[1] nữa.
a=[2,5,6,8,10,12,15] a[2]+a[6]=17>X⇒XCó thể thấy, tổng của a[6] với các phần tử khác trong các phần tử ta quan tâm đều
lớn hơn x. Vì thế ta khơng quan tâm đến a[6] nữa.
a=[2,5,6,8,10,12,15]
Như vậy, tại một thời điểm bất kỳ, những phần tử chúng ta cần quan tâm đến sẽ là
các phần tử trong đoạn [i,j] nào đó.
Ta có một số nhận xét sau:
Nếu i=j, trong mảng A khơng tồn tại hai vị trí khác nhau mà tổng hai phần tử ở đó có giá

•

trị là X.

•

Ngược lại:
10


-

Nếu a[i]+a[j]=X, ta đã tìm được hai vị trí cần tìm (i và j).

-

Nếu a[i]+a[j]
đó là các phần tử trong đoạn [i+1,j].
Nếu a[i]+a[j]>X, không quan tâm đến a[j] nữa và các phần tử chúng ta cần quan tâm

-

đó là các phần tử trong đoạn [i,j−1].
Thuật tốn:
Từ những phân tích vừa rồi ta có giải pháp sử dụng hai con trỏ như sau:
Một con trỏ (i) được đặt ở đầu mảng A, con trỏ còn lại (j) được đặt ở cuối mảng A.
- Nếu tổng của hai phần tử ở hai vị trí con trỏ
+ Nhỏ hơn X: tăng vị trí con trỏ i lên một đơn vị.
+ Lớn hơn X: giảm vị trí con trỏ j đi một đơn vị.
Tiếp tục di chuyển cho đến khi hai con trỏ gặp nhau.
Khi con trỏ chưa gặp nhau mà tổng ở hai vị trí con trỏ có giá trị là X thì ta đã tìm được hai
vị trí cần tìm (i và j), kết thúc chương trình.
3.2.2. Chương trình

#include <bits/stdc++.h>
using namespace std;
int main()
{
long long n,x,a[100000];
cin >> n>>x;
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)
{
11


cout << i << " " << j;
return 0;
}
if (a[i] + a[j] < x)
i += 1;
else
j -= 1;
}
cout << "No solution";
}

3.2.3. Độ phức tạp thuật tốn
Vị trí con trỏ i ln tăng, vị trí con trỏ j thì ln giảm.

Hơn nữa, sự thay đổi vị trí hai con trỏ này sẽ dừng lại khi tổng hai phần tử ở hai vị
trí con trỏ có tổng là X hay khi vị trí i bằng vị trí j.
Vì thế, việc thay đổi vị trí hai con trỏ sẽ khơng q n lần, độ phức tạp của giải pháp
là O(n).

3.3. Ví dụ 3
Length.cpp
Cho dãy số nguyên dương a có n phần tử. Hãy tìm độ dài đoạn con dài nhất trong
dãy sao cho tổng các phần tử trong đoạn này không quá s.
Dữ liệu đảm bảo các phần tử trong dãy a đều có giá trị khơng q s.
Giới hạn: 1 ≤ 𝑛 ≤ 106 , 1 ≤ 𝑎𝑖 ≤ 109 , 𝑠 ≤ 1018.
Dữ liệu vào:
• Dịng đầu tiên chứa số ngun n, s.
• Dịng tiếp theo lần lượt chứa a1, a2, ..., an. Hai số cạnh nhau trên một dòng cách nhau
bởi khoảng trắng.
Kết quả:
12


• Ghi ra độ dài đoạn con dài nhất trong dãy sao cho tổng các phần tử trong đoạn này
không quá s.
Ví dụ:
Input

Output

7 20

4

2653689

3.3.1. Hướng dẫn
Để dễ dàng phân tích, ta tạm gọi:
- sum(l,r) là tổng các phần tử trong đoạn [l,r].
- Một đoạn con [l,r] là đoạn con "tốt" nếu sum(l,r) ≤ s
Qua đây, bài toán của chúng ta sẽ là tìm độ dài đoạn con "tốt" dài nhất.
Vì dãy a là một dãy số nguyên dương cho nên:
- sum(1,r)>sum(2,r)>…>sum(r−1,r)>sum(r,r).
- Nếu đoạn con [l,r] là đoạn con "tốt" thì với mọi x≥l, đoạn [x,r] là đoạn con "tốt".
- Nếu đoạn con [l,r] khơng là đoạn con "tốt" thì với mọi x≤l, đoạn [x,r] không là đoạn con
"tốt".
Với r là một vị trí bất kỳ, nếu như l là vị trí nhỏ nhất sao cho đoạn [l,r] là một đoạn "tốt"
thì:
- Mọi x≥l thì đoạn con [x,r] là một đoạn "tốt".
- Mọi xđoạn con [l,r] là một đoạn con "tốt" dài nhất trong các đoạn con "tốt" có vị trí kết thúc tại
r.
Từ đó, với mỗi r từ 1 đến n, nếu ta xác định được vị trí l, ta có thể biết được độ dài của đoạn
con "tốt" dài nhất của dãy a.
Hãy cùng nhận xét vị trí của l với mỗi r từ 1 đến n qua ví dụ sau đây:
Cho trước dãy a=[2,6,5,3,6,8,9] và s=20
•

r=1→l=1
13


a=[2,6,5,3,6,8,9]
sum(l,r)=2

•

r=2→l=1
a=[2,6,5,3,6,8,9]
sum(l,r)=8

•

r=3→l=1
a=[2,6,5,3,6,8,9]
sum(l,r)=13

•

r=4→l=1
a=[2,6,5,3,6,8,9]
sum(l,r)=16

•

r=5→l=2
a=[2,6,5,3,6,8,9]
sum(l,r)=20

•

r=6→l=4
a=[2,6,5,3,6,8,9]
sum(l,r)=17

•

r=7→l=6
a=[2,6,5,3,6,8,9]
sum(l,r)=17
r

l

Độ dài đoạn con

1

1

1

2

1

2

3

1

3

4

1

4

5

2

4

6

4

3
14


r

l

Độ dài đoạn con

7

6

2

Độ dài của đoạn con "tốt" dài nhất của dãy là giá trị lớn nhất của độ dài các đoạn
con "tốt" dài nhất với vị trí kết thúc từ 1 đến n.
Ở đây, độ dài đoạn con "tốt" dài nhất của dãy là 4.
Qua ví dụ vừa rồi, ta thấy rằng, vị trí l đối với các giá trị r từ 1 đến n có giá trị khơng
giảm.
Thật vậy, với mọi x<l thì sum(x,r)>s⇒sum(x,r+1)>s, vì thế giá trị l đối với r+1 phải
không quá giá trị l đối với r.
Hơn nữa vì các phần tử trong dãy a đều có giá trị khơng q s cho nên ln tồn tại
vị trí l≤r sao cho đoạn [l,r] là một đoạn "tốt".
Thuật tốn:
Với những phân tích như trên, ta có giải quyết bài tốn với phương pháp hai con trỏ
như sau:
Hai con trỏ l và r sẽ đặt ở vị trí 1.
Hai con trỏ này được thể hiện như hai vị trí l, r như ở trên phần phân tích.
Di chuyển lần lượt con trỏ r từ 1 đến n.
Sau mỗi lần di chuyển con trỏ r, nếu
•

sum(l,r)≤s: giữ ngun vị trí con trỏ l.

•

sum(l,r)>s: tăng dần vị trí con trỏ l cho đến khi sum(l,r)≤s.

Hiện tại với vị trí con trỏ l và r, ta biết đoạn "tốt" dài nhất với vị trí kết thúc tại r là đoạn
[l,r].
Độ dài đoạn con "tốt" dài nhất chính là giá trị độ dài lớn nhất của các đoạn "tốt" dài nhất
với vị trí kết thúc tại r, với mỗi r từ 1 đến n.
3.3.2. Chương trình

Để có thể tính được tổng các phần tử từ l đến r trong khi l và r đang di động, ta sẽ sử
dụng biến sum để lưu lại tổng của đoạn [l,r] hiện tại.
Sau khi di chuyển r sang phải, biến sum sẽ cộng thêm giá trị a[r].
15


Trước khi di chuyển l sang phải, biến sum sẽ trừ đi giá trị a[l].
#include <bits/stdc++.h>
using namespace std;
long long a[100000],n,sum,s;
int main()
{
cin>>n>>s;
for(int i=1;i<=n;i++)
cin>>a[i];
int ans = 0, 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;
}
3.3.3. Độ phức tạp

Vị trí con trỏ r ln tăng, vị trí con trỏ l luôn tăng và luôn tăng không quá giá trị r.
Hơn nữa, mỗi vị trí l và r tăng khơng q n lần.
Vì thế độ phức tạp của giải pháp là O(n).

3.4. Ví dụ 4
DÃY CON DÀI NHẤT
16


Cho dãy số nguyên dương a1, a2, ...., an trong đó các giá trị ai ≤m. Hãy tìm dãy con dài nhất
của a gồm các số hạng liên tục mà trong đó mỗi giá trị xuất hiện khơng q K lần.
Input: File SUBSEQ.INP
• Dịng đầu tiên chứa 3 số N, M, K (1 ≤N, M≤105)
• Các dịng tiếp theo lần lượt chứa a1, a2, ..., an. Hai số cạnh nhau trên một dòng cách
nhau bởi khoảng trắng.
Output: File SUBSEQ.OUT một số nguyên duy nhất là độ dài dãy con tìm được
Ví dụ:
SUBSEQ.INP

SUBSEQ.OUT

5 10 2

4

11122
3.4.1. Hướng dẫn
Cũng tương tự ví dụ 3. Để giải bài tốn này ta có thể sử dụng kỹ thuật 2 con trỏ.
Một con trỏ i đặt ở đầu mảng vị trí 1 (i=1) và một con trỏ j đặt ở vị trí 2 (j=2)
Sử dụng mảng đếm phân phối d để lưu giá trị của mảng a[i] và mảng a[j]

- d[a[j]++
- Chừng nào d[a[j]] > k thì ta giảm d[a[i]]-- và tăng i++.
- Cập nhập lại đoạn con dài nhất res = max(j-i+1,res) sau đó tăng j++.
3.4.2. Chương trình
#include <bits/stdc++.h>
#define fi(i,a,b) for(int i=a;i<=b;i++)
#define maxn 100009
using namespace std;
int n,m,k,d[maxn],a[maxn],res,dem;
int main()
{
ios_base :: sync_with_stdio(0);
cout.tie(0);
17


cin >> n >> m >> k;
fi(i,1,n)
cin >> a[i];
d[a[1]]++;
int i=1,j=2;
while(i<=j && j<=n)
{
d[a[j]]++;
while(d[a[j]] > k && i<=j)
{
d[a[i]]--;
i++;
}
res=max(res,j-i+1);

j++;
}
cout << res;
}

3.4.3. Độ phức tạp thuật toán
- Độ phức tạp thuật toán là O(n)

3.5. Ví dụ 5
Trị chơi với dãy số (sgame.*)
Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây. Mỗi bạn chọn trước
một dãy số gồm n số nguyên. Giả sử dãy số mà bạn thứ nhất chọn là:
𝑏1 , 𝑏2 , . . . , 𝑏𝑛
còn dãy số mà bạn thứ hai chọn là
𝑐1 , 𝑐2 , . . . , 𝑐𝑛
18


Mỗi lượt chơi mỗi bạn đưa ra một số hạng trong dãy số của mình. Nếu bạn thứ nhất
đưa ra số hạng 𝑏𝑖 (1 ≤ 𝑖 ≤ 𝑛), còn bạn thứ hai đưa ra số hạng 𝑐𝑗 (1 ≤ 𝑗 ≤ 𝑛) thì giá của
lượt chơi đó sẽ là |𝑏𝑖 + 𝑐𝑗 |. Ví dụ: Giả sử dãy số bạn thứ nhất chọn là 1, -2; còn dãy số mà
bạn thứ hai chọn là 2, 3. Khi đó các khả năng có thể của một lượt chơi là (1, 2), (1, 3), (-2,
2), (-2, 3). Như vậy, giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể là 0 tương
ứng với giá của lượt chơi (-2, 2).
Yêu cầu
Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể.
Dữ liệu: SGAME.INP
•

Dịng đầu tiên chứa số nguyên dương n (𝑛 ≤ 105 )

•

Dịng thứ hai chứa dãy số ngun 𝑏1 , 𝑏2 , . . . , 𝑏𝑛 (|bi| ≤ 109, i=1, 2, ..., n)

•

Dịng thứ hai chứa dãy số ngun c1, c2, ..., cn (|ci| ≤ 109, i=1, 2, ..., n)

Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách.
Kết quả: SGAME.OUT
Ghi ra giá nhỏ nhất tìm được.
Ràng buộc
•

60% số tests ứng với 60% số điểm của bài có 1 ≤ n ≤ 1000.

Ví dụ
SGAME.INP

SGAME.OUT

2

0

1 -2
23

3.5.1. Hướng dẫn giải thuật

Cách 1: Cách đơn giản sử dụng 2 vịng lặp for để giải quyết bài tốn, cách này chương trình
chạy chậm. Độ phức tạp thuật tốn là O(𝑛2 ).
Cách 2: Cải tiến sử dụng kỹ thuật 2 con trỏ.
- Săp xếp 2 mảng theo chiều tăng dần.
19


- Sử dụng kỹ thuật 2 con trỏ. Một con trỏ i duyệt từ đầu mảng a và một con trỏ j duyệt cuối
mảng b. Nếu Sum = a[i] + b[j] mà lớn hơn 0 thì giảm j và cập nhật lại giá trị nhỏ nhất.
Ngược lại thì tăng i và cập nhập lại giá trị nhỏ nhất.
3.5.2. Chương trình
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int a[n], b[n];
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
cin >> b[i];
sort(a, a + n);
sort(b, b + n);
int res = INT_MAX;
int i = 0, j = n - 1;
while (i < n && j >= 0)
{
int sum = a[i] + b[j];
if (sum < 0)

{
i++;
res = min(res, 0 - sum);
}
if (sum > 0)
{
20


j--;
res = min(res, sum);
}
if (sum == 0)
{
res = 0;
break;
}
}
cout << res;
}

3.5.3. Độ phức tạp thuật toán
Độ phức tạp thuật toán: O(nlogn)
4. Bài tập ứng dụng
4.1. Bài 1
Apartments
Có n ứng viên và m căn hộ miễn phí. Hãy phân bổ các căn hộ để sao cho số người
có được căn hộ là nhiều nhất.
Mỗi ứng viên có u cầu về kích thước căn hộ họ mong muốn nhận được, và họ sẽ
chấp nhận bất kì căn họ nào mà có kích thước gần với kích thước mong muốn nếu như

khơng có căn hộ nào đúng kích thước họ u cầu.
Input:
• Dịng đầu ghi 3 số ngun n, m, k
• Dịng thứ hai ghi n số nguyên cách nhau bởi dấu cách 𝑎1 , 𝑎2 , … , 𝑎𝑛 là kích thước
mong muốn của mỗi ứng viên. Nếu kích thước mong muốn của ứng viên là x, họ sẽ
chấp nhận các căn hộ có kích thước trong đoạn x-k đến x+k

21


• Dòng cuối cùng ghi m số nguyên cách nhau bởi dấu cách 𝑏1 , 𝑏2 , … , 𝑏𝑚 là kích thước
của các căn hộ.
Output:
• In ra một số nguyên là số lượng ứng viên nhận được căn hộ.
Ràng buộc:
• 1 ≤ 𝑛, 𝑚 ≤ 2.105
• 1 ≤ 𝑎𝑖 , 𝑏𝑖 ≤ 109
• 1 ≤ 𝑘 ≤ 109
•
Ví dụ:
Input

Output

435

2

60 45 80 60
30 60 75

4.1.1. Hướng dẫn:
- Chúng ta có thể sử dụng thuật toán tham lam kết hợp kỹ thuật hai con trỏ.
- Đặt a là dãy các ứng viên, b là dãy các căn hộ.
- Đầu tiên sắp xếp lại các ứng viên và căn hộ.
- Dùng 2 con trỏ i và j (khởi tạo i=1 và j=1), chúng ta kiểm tra như sau:
• Nếu a[i] – b[j] ≤ k (chúng ta đã tìm thấy một căn hộ phù hợp cho người nộp đơn
hiện tại). Do đó, tăng i, tăng j, và đưa ra câu trả lời.
• Ngược lại, b[j] quá lớn hoặc quá nhỏ so với a[i] chúng ta có thể tăng i hoặc j cho
phù hợp.
4.1.2. Chương trình

22


#include <bits/stdc++.h>
using namespace std;
int n,m,k,a[200001],b[200001],res;
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=m;i++)
cin>>b[i];
sort(a+1,a+n+1);
sort(b+1,b+m+1);
int i=1,j=1;
while(i<=n&&j<=m)
{

if(abs(a[i]-b[j])<=k)
{
i++;
j++;
res++;
//cout<}
else
if(a[i]-b[j]>k) j++;
else i++;
}
cout<return 0;
}

23


4.1.3. Độ phức tạp thuật toán
- Độ phức tạp thuật tốn là: O(nlogn)
4.2. Bài 2
Ferris Wheel
Có n đứa trẻ, chúng muốn có một chiếc bánh xe Ferris (đu quay), bạn hãy tìm chỗ
cho mỗi đứa trẻ? Mỗi chỗ có thể ngồi 1 hoặc 2 trẻ, và tổng trọng lượng trên mỗi chỗ không
vượt quá x. Bạn được cho biết cân nặng của mỗi đứa trẻ.
Hỏi số lượng chỗ ngồi ít nhất mà cần dành cho tất cả n đứa trẻ là bao nhiêu?
Input:
• Dịng đầu ghi 2 số ngun n, x
• Dịng thứ hai ghi n số ngun cách nhau bởi dấu cách 𝑝1 , 𝑝2 , … , 𝑝𝑛 là trọng lượng
của mỗi đứa trẻ.

Output:
• In ra một số nguyên là số lượng chỗ ngồi nhỏ nhất dành cho n đứa trẻ
Ràng buộc:
• 1 ≤ 𝑛 ≤ 2.105
• 1 ≤ 𝑥 ≤ 109
• 1 ≤ 𝑝𝑖 ≤ 𝑥
Ví dụ:
Input

Output

4 10

3

7239

4.2.1. Hướng dẫn
Vì mỗi chỗ ngồi có thể chứa 1 hoặc 2 trẻ em nên với mỗi chỗ ngồi, chúng ta có thể có các
cách làm như sau:
• Ghép đứa trẻ nhẹ nhất với đứa trẻ nặng nhất có thể, mà không bị vượt quá trọng
lượng.
24


• Nếu khơng thể ghép được, thì chúng ta chỉ bao gồm những đứa trẻ nhẹ nhất.
Những người còn lại chưa ghép đơi đều có chỗ ngồi của riêng mình. Việc thực hiện dưới
đây cũng sử dụng phương pháp như trên.
• Ghép đơi đứa trẻ nặng nhất với đứa trẻ nhẹ nhất nếu có thể.
• Nếu khơng thể ghép được, thì chúng ta chỉ bao gồm những đứa trẻ nặng nhất.

Thuật tốn:
• Sắp xếp lại trọng lượng của những đứa trẻ.
• Sử dụng 2 con trỏ một con trỏ i xuất phát từ đầu mảng p và một con trỏ j xuất phát
cuối mảng p.(mảng p là mảng trọng lượng những đứa trẻ)
• Nếu tổng cân nặng của 2 bé vượt quá x, chúng ta chuyển sang đứa trẻ nhẹ hơn (if
(p[i] + p[j] >x) j--)
• Ngược lại nếu thỏa mãn điều kiện thì tăng số chỗ ngồi sử dụng, đánh dấu họ đã có
chỗ ngồi, chuyển sang các vị trí tiếp theo.
Q trình được lặp đi lặp lại đến khi i>j thì dừng.
Duyệt lại dãy để tính số em chưa có chỗ ngồi, để biết tổng số chỗ ngồi của bài tốn.
4.2.2. Chương trình
#include <bits/stdc++.h>

using namespace std;

const int maxn=2e5+10;

int n,x,p[maxn],i,j,ans;
// Theo doi so luong tre da co cho ngoi cua rieng minh chua
bool have_gondola_yet[maxn];

25