CẤU TRÚC DỮ LIỆU PAIR TRONG C++

1. Pair là gì?

Pair là một cấu trúc dữ liệu trong thư viện chuẩn C++ dùng để gom hai giá trị thành một đối tượng duy nhất.

Ví dụ trong hình học, một điểm trên mặt phẳng Oxy có thể lưu bằng hai số x và y. Khi đó ta có thể dùng pair<int,int> để lưu tọa độ.

So sánh cách dùng struct và pair

struct toado {
    int x; // hoành độ
    int y; // tung độ
};

toado p;

pair<int, int> p;

// quy ước:
// p.first  là hoành độ x
// p.second là tung độ y

3. Truy cập dữ liệu bằng first và second

Muốn lấy hoặc gán giá trị cho hai thành phần của pair, ta dùng first và second.

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

int main() {
    pair<int, int> p;

    cin >> p.first >> p.second;
    cout << p.first << " " << p.second;

    return 0;
}

4. Khởi tạo pair và hàm make_pair()

Cách 1: Khởi tạo trực tiếp

pair<int, char> p(1, 'a');

cout << p.first;   // 1
cout << p.second;  // a

Cách 2: Gán bằng make_pair()

pair<int, int> p;
p = make_pair(1, 2);

cout << p.first << " " << p.second; // 1 2

Cách 3: Gán bằng dấu ngoặc nhọn

pair<string, int> hs;
hs = {"AN", 10};

cout << hs.first << " " << hs.second; // AN 10

5. Các phép so sánh pair

Pair có thể dùng trực tiếp các toán tử so sánh:

== != < > <= >=

pair<int, int> a = {1, 20};
pair<int, int> b = {1, 18};

if (a > b)
    cout << "a lon hon b";

6. swap() và sort() với pair

Đổi chỗ hai pair

pair<int, int> p1, p2;
p1 = {1, 2};
p2 = {5, 1};

swap(p1, p2);

cout << p1.first << " " << p1.second << '\n'; // 5 1
cout << p2.first << " " << p2.second << '\n'; // 1 2

Sắp xếp mảng pair

Nếu dùng sort(a, a+n), C++ sẽ tự sắp xếp tăng dần theo first, nếu first bằng nhau thì tăng dần theo second.

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

int main() {
    pair<int, int> a[6];

    a[1] = make_pair(1, 2);
    a[2] = make_pair(8, 5);
    a[3] = make_pair(6, 2);
    a[4] = make_pair(2, 3);
    a[5] = make_pair(3, 6);

    sort(a + 1, a + 6);

    for (int i = 1; i <= 5; i++)
        cout << a[i].first << " " << a[i].second << endl;
}

7. Mảng pair và pair lồng nhau

Mảng pair

pair<int, int> p[100];

// p[0], p[1], ..., p[99]
// mỗi phần tử đều có p[i].first và p[i].second

Pair lồng nhau

pair<int, pair<int, int>> p;

p.first = 10;
p.second.first = 20;
p.second.second = 30;

8. Bài tập luyện tập PAIR

Các bài dưới đây được biên soạn lại từ tài liệu gốc, phù hợp đưa vào OJ để học sinh luyện tập.

Bé Bin mới học tên các đồ vật gồm 2 từ như: tu lanh, xe dap, may bay. Hãy đảo ngược thứ tự hai từ của mỗi tên đồ vật.

Dữ liệu

Dòng đầu là số nguyên dương N là số tên đồ vật, N ≤ 50. N dòng tiếp theo, mỗi dòng gồm đúng 2 từ, mỗi từ không quá 5 ký tự, viết thường, không dấu.

Kết quả

In ra N dòng, mỗi dòng là tên sau khi đảo hai từ.

3
tu lanh
xe dap
nha may

lanh tu
dap xe
may nha

Một công ty có N khoản doanh thu, mỗi khoản gồm tiền đầu tư và tiền lãi. Hãy sắp xếp doanh thu tăng dần theo tiền lãi. Nếu tiền lãi bằng nhau thì sắp xếp giảm dần theo tiền đầu tư.

Dữ liệu

Dòng đầu là số nguyên dương N. N dòng sau, mỗi dòng gồm hai số nguyên: đầu_tư và lãi, mỗi số từ 0 đến 1000.

Kết quả

In ra N dòng là các khoản doanh thu sau khi sắp xếp.

4
100 200
130 180
450 300
210 300

130 180
100 200
450 300
210 300

Trong một bữa tiệc, mỗi cặp nhảy gồm một bạn nam cao x và một bạn nữ cao y. Độ chênh lệch của cặp là |x - y|. Hãy tìm độ chênh lệch xuất hiện nhiều nhất. Nếu có nhiều độ chênh lệch cùng xuất hiện nhiều nhất, chọn độ chênh lệch nhỏ nhất.

Dữ liệu

Dòng đầu là số nguyên dương N ≤ 10³. N dòng tiếp theo, mỗi dòng gồm hai số nguyên x, y, với 1 ≤ x, y ≤ 10³.

Kết quả

Dòng đầu in ra độ chênh lệch được chọn. Các dòng tiếp theo in các cặp có độ chênh lệch đó theo thứ tự dữ liệu vào.

4
5 6
7 8
5 3
9 10

1
5 6
7 8
9 10

Kỳ thi giữa kỳ gồm 2 môn Tin và Thể dục. Với mỗi học sinh, cần xác định thứ hạng tổng điểm của học sinh đó trong trường. Thứ hạng của một học sinh bằng số học sinh có tổng điểm cao hơn cộng thêm 1.

Dữ liệu

Dòng đầu là số nguyên dương N ≤ 10². N dòng tiếp theo gồm: tên viết tắt của học sinh, điểm Tin x và điểm Thể dục y, với 1 ≤ x, y ≤ 100.

Kết quả

In ra N dòng theo thứ tự dữ liệu vào, mỗi dòng gồm tên học sinh và thứ hạng.

6
NA 3 5
MT 6 7
TB 5 5
MH 8 8
YN 6 2
PQ 4 3

NA 4
MT 2
TB 3
MH 1
YN 4
PQ 6

Công ty nhận N dự án. Dự án i cần chi phí đầu tư a_i và sau khi hoàn thành thu về b_i. Công ty được thực hiện dự án theo thứ tự tùy ý. Hãy tìm số vốn ban đầu ít nhất cần có để có thể hoàn thành tất cả dự án.

Dữ liệu

Dòng đầu chứa n ≤ 10⁵. Dòng thứ hai chứa n số a₁, a₂, ..., a_n. Dòng thứ ba chứa n số b₁, b₂, ..., b_n, các giá trị không quá 10⁹.

Kết quả

In ra một số nguyên là vốn ban đầu tối thiểu.

6
6 3 1 2 4 9
2 4 3 1 3 2

11

Tổng kết kiến thức

9. Cách nhúng bài giảng này vào OJ

Sau khi đưa file PAIR_LIEN_KET.htm lên server, ví dụ tại:

https://hvojbd.ddns.net/docs/LTBT/PAIR_LIEN_KET.htm

Trong phần mô tả bài/kỳ thi của OJ, dán đoạn sau:

<iframe
src="https://hvojbd.ddns.net/docs/LTBT/PAIR_LIEN_KET.htm"
width="100%"
height="850px"
frameborder="0">
</iframe>