SKKN Sử dụng cấu trúc dữ liệu set, map, pair và một số hàm trong C++ trong bồi dưỡng học sinh giỏi cho bài toán tìm kiếm, sắp xếp với độ phức tạp O(n) hoặc O(logn)

Cụ thể các đề các năm như sau:
Đề thi học sinh giỏi năm học 2010-2011 tỉnh nghệ An
Bài toán: (5 điểm) TẦN SỐ
Cho dãy số nguyên dương, số lần xuất hiện của một số được gọi tần số của số nguyên đó. Hãy tìm số nguyên dương có tần số cao nhất và tần số tương ứng của nó.
Dữ liệu vào cho từ file văn bản BAI1.INP bao gồm:
Dòng đầu là số N (1≤ N ≤ 10000) là số lượng các số nguyên trong dãy.
Mỗi dòng trong N dòng tiếp theo chứa số nguyên M (1≤ M ≤ 1000) trong dãy. Kết quả ghi ra file văn bản BAI1.OUT, gồm 2 số nguyên viết trên một dòng, số thứ nhất ghi số nguyên có tần số cao nhất, số thứ 2 là tần số của nó (trong trường hợp có nhiều số nguyên có tần số cao nhất bằng nhau, hãy đưa ra số nguyên nhỏ nhất và tần số của nó). Hai số cách nhau một ký tự trắng.
Ví dụ:
BAI1.INP
BAI1.OUT
BAI1.INP
BAI1.OUT
9
1
2
5
6
3
7
2
5
2
2 3
7
2
4
6
7
7
2
4
2 2

Với bài toán trên yêu cầu đưa ra kết quả số nguyên có tần số xuất hiện nhiều nhất (trong trường hợp có nhiều số nguyên có tần số cao nhất bằng nhau, hãy đưa ra số nguyên nhỏ nhất và tần số của nó). Bài toán này ta nghĩ ngay đến cặp key- value. Trong đó key chính là số nguyên còn value chính là tần số xuất hiện. Tại sao ở đây ta sử cấu trúc dữ liệu map. Bởi vì mỗi key là duy nhất nên có nhiều số nguyên giống nhau thì chỉ là 1 key tương ứng số nguyên đó. Còn xuất hiện nhiều lần chính là tần số tương ứng ( value). Trong trường hợp cùng value thì đưa ra key nhỏ nhất. Mà key trong map đã tự sắp xếp theo thứ thự từ bé đến lớn. Do đó để tìm value Max ta có đoạn lệnh như sau:
int ln=0;
if(it.second>ln)
{
ln=it.second; kq=it.first;
}
Chương trình hoàn thiện #include using namespace std;
long long x,kq, ln=0;
int main()
{
map m; int n;
freopen("bai1.inp","r",stdin);
freopen("bai1.out","w",stdout); cin>>n;
for(int i=1; i<=n;i++)
{
cin>>x; m[x]++;
}
for(auto it:m) if(it.second>ln)
{
ln=it.second; kq=it.first;
}
cout<<kq<<" "<<ln<<'\n';
}
Đề thi học sinh giỏi năm học 2013-2014 tỉnh nghệ An
Bài toán.	LAPTRINH
Trong cuộc thi lập trình có N bài thi giải đúng yêu cầu đặt ra. Ban tổ chức quyết định trao phần thưởng đặc biệt cho bài thi tốt nhất, đó là bài thi có thời gian chạy chương trình ít nhất. Cho biết bài thi thứ i (1< i < N) có thời gian chạy là một số nguyên ai (tính theo đơn vị centisecond, 1centisecond = 1/100 giây).
Yêu cầu: Hãy cho biết thời gian của bài thi được trao thưởng và có bao nhiêu bài thi được trao thưởng.
Dữ liệu: Vào từ file văn bản LAPTRINH.INP
Dòng 1 chứa số nguyên dương N (N < 100).
Dòng 2 chứa N số nguyên a1, ..., an (0 < ai < 100).
Kết quả: Ghi ra file văn bản LAPTRINH.OUT
Dòng thứ nhất chứa một số nguyên là thời gian ít nhất tìm được
Dòng thứ hai chứa một số nguyên là số bài thi cùng đạt thời gian ít nhất.
Ví dụ.
LAPTRINH.INP
LAPTRINH.OUT
5
10 8 12 8 11
8
2

Giải thích test ví dụ: thời gian ít nhất là 8 và có 2 bài cùng thời gian đó.
Với bài toán này chúng ta sử dụng map một cách đơn giản vì để tìm ra thời gian ngắn nhất cùng số lần xuất hiện. Nghĩa là tìm các value max nhưng key nhỏ nhất. Trong map đã sắp xếp các key theo thứ thự tăng dần nên ta chỉ cần lấy ra key đầu tiên của map chính là thời gian chạy ít nhất.
Cụ thể chương trình như sau: #include using namespace std;
int n;
int a[100006]; int main()
{
map m; freopen("laptrinh.inp","r",stdin); freopen("laptrinh.out","w",stdout); cin>>n;
for(int i=1; i<=n;i++)
{
cin>>a[i];
m[a[i]]++;
}
for(auto it:m)
{
cout<<it.first<<" "<<it.second<<'\n'; break;
} }
Tương tự đề thi HSG tỉnh Nghệ An năm 2018-2019 có bài toán bán hàng tự động
Bài toán:	BÁN HÀNG TỰ ĐỘNG
Tại một điểm bán hàng tự động, mỗi loại hàng được gán tương ứng với một số nguyên dương gọi là mã hàng, hai loại hàng khác nhau có mã hàng khác nhau. Mỗi lần khách mua hàng, máy chỉ bán một loại hàng với số lượng là 1 sản phẩm và ghi vào nhật kí của máy mã loại hàng đã bán. Sau khi kết thúc một đợt bán hàng, nhật kí bán hàng của máy là một dãy số nguyên dương. Người quản lí cần thống kê xem loại hàng nào đã được máy bán nhiều nhất, số lượng hàng loại đó đã bán là bao nhiêu? Bạn hãy viết chương trình giúp người quản lý tìm loại hàng đó.
Dữ liệu: Vào từ file văn bản DEMHANG.INP:
Dòng đầu tiên ghi số nguyên dương 𝑁 (𝑁 ≤ 10000) là số lượng hàng mà máy đã bán.
N dòng tiếp theo mỗi dòng ghi một số nguyên dương là mã loại hàng đã bán trong nhật kí của máy. Giá trị các số nguyên dương không vượt quá 106.
Kết quả: Đưa ra file văn bản DEMHANG.OUT chỉ một dòng duy nhất ghi mã loại hàng đã bán nhiều nhất và số lượng hàng loại đó mà máy đã bán, hai giá trị này cách nhau một ký tự trống. Nếu như có nhiều loại hàng có cùng số lượng bán nhiều nhất thì in ra mã loại hàng có giá trị bé nhất.
Ví dụ:
DEMHANG.INP
DEMHANG.OUT
11
1
2
2
3
2
4
5
2
6
7
6
2 4

Hạn chế: - 60% số test có giá trị các mã số trong phạm vị từ 1 đến 103.
- 40% số test có giá trị các mã số trong phạm vi từ 1 đến 106.
Bài toán này hạn chế số test với giá trị các mã đến 106. Nếu giá trị các mã hàng sử dụng mảng lưu là các chỉ số mảng, các value tương ứng là tần suất xuất hiện chỉ số đó thì bài toán hạn chế mã số không vượt quá giá trị 107. Vậy nếu chúng ta sử dụng cấu trúc dữ liệu này có thể sử dụng đến 1018 mà vẫn đảm bảo thờ gian chạy 1 giây với giá trị lớn. Vì độ phức tạp O(logn). Đồng thời không cần mảng để lưu, do đó không hạn chế số chỉ số phần tử mảng.
Ta có chương trình bài toán #include using namespace std;
long long x,kq, ln=0; int main()
{
map m; int n;
freopen("demhang.inp","r",stdin); freopen("demhang.out","w",stdout); cin>>n;
for(int i=1; i<=n;i++)
{
cin>>x; m[x]++;
}
for(auto it:m) if(it.second>ln)
{
ln=it.second; kq=it.first;
}
cout<<kq<<" "<<ln<<'\n';
}
Với bài toán trên yêu cầu: Nếu như có nhiều loại hàng có cùng số lượng bán nhiều nhất thì in ra mã loại hàng có giá trị lớn nhất. Ở đây thầy cô chỉ cần đổi ở câu lệnh if này có dấu bằng xảy ra cụ thể:
if(it.second>=ln)
{
ln=it.second; kq=it.first;
}
cout<<kq<<" "<<ln<<'\n';
}
Một số dạng bài toán ứng dụng cấu trúc dữ liệu map
Bài 1: Cho một danh sách các số điện thoại kèm theo tên của chủ thuê bao đó. Yêu cầu đầu vào là một số điện thoại (key), hãy đưa ra tên của chủ thuê bao (value)
Bài 2: Cho danh sách thể hiện lịch sử đi muộn của các nhân viên một công ty nào đó. Hãy tìm xem nhân viên (key) nào có số lần đi muộn (value) nhiều nhất?
Bài 3: Cho một danh sách các IP kèm theo các domain. Hãy trả ra ip (value) tương ứng domain (key) hoặc ngược lại trong thời gian nhanh nhất?
Với các bài toán này, bạn có thể sử dụng 2 mảng dữ liệu có cùng độ dài. Một mảng bạn lưu danh sách key, một mảng bạn lưu danh sách các value tương ứng với key đó (cùng chỉ số truy cập mảng). Khi bạn cần tìm value của một key nào đó, bạn duyệt mảng key, tìm chỉ số của phần tử trong mảng có giá trị bằng key cần tìm rồi trả ra giá trị tương ứng ở mảng value. Mã giả của đoạn code này như sau:
for (int i=0; i<keysArray.size(); i++) if (keysArray[i] == key) return valuesArray[i];return "notFound";
Với đoạn mã như trên, độ phức tạp thuật toán sẽ là O(N) (do bạn phải duyệt cả mảng keysArray để tìm cái key bạn muốn). Để tăng tốc độ cho đoạn mã này, bạn có thể cải tiến hàm tìm kiếm theo phương pháp tìm kiếm nhị phân (với điều kiện mảng keysArray đã được sắp xếp). Tất nhiên cách làm này sẽ tốn công cài đặt hơn rất nhiều lần so với việc bạn sử dụng map (hay dictionary) thông qua dòng lệnh duy nhất sau:
if (mymap.find(key) != mymap.end()) return mymap[key];else return "notFound";
Không chỉ là dễ cài đặt và sử dụng, việc sử dụng map còn đáp ứng tốc độ chạy chương trình khá cao.
Tóm lại với các bài toán về tần suất xuất hiện và có 2 cặp giá trị tương ứng ta nên sử dụng cấu trúc dữ liệu map vì xử lý đơn giản với các kiểu dữ liệu không chỉ kiểu số mà kiểu xâu, ký tự. Đồng thời độ phức tạp chỉ O(logn).
Kiểu dữ liệu Set
Chắc bạn đã biết rất nhiều cấu trúc dữ liệu cơ bản rồi. Cấu trúc dữ liệu đơn giản nhất mà mình nghĩ ai cũng biết đó là mảng (array). Sau đó đa phần sẽ biết
tới queue và stack. Còn ở đây mình sẽ giới thiệu về set
Set cũng là 1 cấu trúc dữ liệu để lưu một danh sách các phần tử cùng kiểu dữ liệu, trong đó các phần tử không được trùng nhau. Ví dụ như array có thể có các phần tử trùng nhau như {1, 2, 1, 1, 2} nhưng set thì chỉ chứa các phần tử khác nhau {1, 2}
Tại sao set lại chỉ chứa các phần tử khác nhau, ấy là vì khi insert mỗi phần tử x vào trong set, set sẽ kiểm tra và chỉ thêm phần tử đó khi x không có trong set.
Trong khi lập trình các bạn có thể gặp những bài toán tìm max, tìm min của một tập hợp với những truy vấn thêm bớt phần tử. Thông thường sau mỗi truy vấn ta có thể duyệt lại phần tử của tập hợp và mất độ phức tạp O(n). Thay vào đó ta có thể sử dụng cấu trúc dữ liệu set để giải quyết các truy vấn đấy chỉ trong độ phức tạp O(log2n).
a, Set là gì
Set trong C++ là một tập hợp các phần tử duy nhất được sắp xếp theo thứ tự cụ thể, và được sử dụng làm tiêu chuẩn để xử lý các đối tượng chứa nhiều phần tử trong C++.
Khi làm việc với kiểu dữ liệu std::set trong C++, bạn cần nhớ hai tính chất đặc trưng của kiểu dữ liệu này đó là:
+ Mỗi phần tử trong cùng một std::set là duy nhất (hay unique). Điều này có nghĩa rằng nếu bạn không thể lưu trữ hai phần tử có giá trị như nhau trong cùng
một std::set. Ngoài ra thì phần tử trong set không thể thay đổi giá trị, tuy nhiên chúng có thể được chèn hoặc xóa khỏi set.
+ Tất cả các phần trử trong cùng một std::set phải thuộc cùng một kiểu dữ liệu.
Về mặt nội bộ, các phần tử trong set luôn được sắp xếp theo thứ tự cụ thể một cách nghiêm ngặt, được chỉ ra bởi đối tượng so sánh nội bộ của nó. Nếu bạn thêm các phần tử mới không theo thứ tự cụ thể vào một set, chúng sẽ tự động sắp xếp lại theo giá trị trước khi được lưu trữ nội bộ.
Nói tóm lại thì set trong C+++ sẽ giống như một mảng với các phần tử không trùng lặp và luôn được sắp xếp.
Về mặt tố