Khóa học CTDL và GT

Bài 8.4. Multiset và bài toán đếm tần suất

Chào mừng bạn quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Trong các bài trước, chúng ta đã tìm hiểu về Set - một cấu trúc dữ liệu tuyệt vời giúp lưu trữ các phần tử duy nhất. Hôm nay, chúng ta sẽ nâng cấp khái niệm đó lên một bước với Multiset và xem nó hữu ích như thế nào trong một lớp bài toán rất phổ biến: đếm tần suất của các phần tử.

Multiset là gì? Sự khác biệt với Set

Hãy hình dung thế này: một Set giống như một chiếc hộp chỉ cho phép bạn bỏ vào những món đồ khác nhau. Nếu bạn cố gắng bỏ vào một món đồ đã có, nó sẽ không chấp nhận hoặc đơn giản là bỏ qua.

Ngược lại, một Multiset (hay còn gọi là bag - túi) giống như một chiếc túi mua sắm vậy. Bạn có thể bỏ vào bao nhiêu món đồ tùy thích, ngay cả khi chúng giống hệt nhau. Nếu bạn mua 3 quả táo, bạn bỏ cả 3 quả táo vào túi, và chiếc túi ghi nhớ rằng có 3 quả táo.

Về mặt kỹ thuật:

• Set: Là một tập hợp các phần tử, trong đó mỗi phần tử chỉ xuất hiện duy nhất một lần.
• Multiset: Là một tập hợp các phần tử, trong đó một phần tử có thể xuất hiện nhiều hơn một lần.

Ví dụ:

• Set: { 1, 2, 3, 4 }
• Multiset: { 1, 1, 2, 3, 3, 3, 4 }

Như bạn thấy, Multiset cho phép số 1 xuất hiện 2 lần và số 3 xuất hiện 3 lần. Chính khả năng lưu trữ các phần tử lặp lại này làm cho Multiset trở thành một công cụ mạnh mẽ cho các bài toán liên quan đến tần suất.

Multiset trong C++ (std::multiset)

Trong thư viện chuẩn C++, chúng ta có std::multiset nằm trong header <set>. Tương tự như std::set, std::multiset cũng là một cấu trúc dữ liệu dựa trên cây tìm kiếm cân bằng (thường là Red-Black Tree), điều này mang lại các đặc điểm sau:

• Các phần tử được sắp xếp: Mặc định, các phần tử trong std::multiset được sắp xếp theo thứ tự tăng dần (hoặc giảm dần nếu bạn cung cấp Comparator khác).
• Hoạt động cơ bản có độ phức tạp O(log n): Các thao tác như thêm (insert), xóa (erase), tìm kiếm (find), và đếm số lần xuất hiện (count) thường mất thời gian logarithmic so với số lượng phần tử trong multiset.

Hãy xem một ví dụ cơ bản về cách sử dụng std::multiset:

#include <iostream>
#include <set> // Include header cho multiset

int main() {
    // Khai báo một multiset chứa các số nguyên
    std::multiset<int> myMultiset;

    // Thêm các phần tử vào multiset
    myMultiset.insert(10);
    myMultiset.insert(20);
    myMultiset.insert(10); // Thêm lại số 10
    myMultiset.insert(30);
    myMultiset.insert(20); // Thêm lại số 20
    myMultiset.insert(10); // Thêm lại số 10

    // In ra các phần tử trong multiset
    // Lưu ý: std::multiset tự động sắp xếp các phần tử
    std::cout << "Cac phan tu trong multiset (sap xep): ";
    for (int element : myMultiset) {
        std::cout << element << " ";
    }
    std::cout << std::endl; // Output: 10 10 10 20 20 30

    // Tìm kiếm một phần tử
    auto it = myMultiset.find(20);
    if (it != myMultiset.end()) {
        std::cout << "Tim thay it nhat mot phan tu 20." << std::endl;
    } else {
        std::cout << "Khong tim thay phan tu 20." << std::endl;
    }

    // Dem so lan xuat hien cua mot phan tu
    std::cout << "So lan xuat hien cua 10: " << myMultiset.count(10) << std::endl; // Output: 3
    std::cout << "So lan xuat hien cua 20: " << myMultiset.count(20) << std::endl; // Output: 2
    std::cout << "So lan xuat hien cua 50: " << myMultiset.count(50) << std::endl; // Output: 0

    // Xoa mot lan xuat hien cua mot phan tu
    myMultiset.erase(myMultiset.find(10)); // Xoa lan xuat hien dau tien cua 10 duoc tim thay bang find()

    std::cout << "Multiset sau khi xoa mot lan xuat hien cua 10: ";
    for (int element : myMultiset) {
        std::cout << element << " ";
    }
    std::cout << std::endl; // Output: 10 10 20 20 30

    // Xoa tat ca cac lan xuat hien cua mot phan tu
    myMultiset.erase(20); // Xoa tat ca cac phan tu co gia tri 20

    std::cout << "Multiset sau khi xoa tat ca cac lan xuat hien cua 20: ";
    for (int element : myMultiset) {
        std::cout << element << " ";
    }
    std::cout << std::endl; // Output: 10 10 30

    return 0;
}

Giải thích code:

• Chúng ta khai báo myMultiset kiểu std::multiset<int>.
• Hàm insert() cho phép thêm các phần tử, và như bạn thấy, nó chấp nhận các giá trị lặp lại.
• Khi in ra, các phần tử được tự động sắp xếp: 10 10 10 20 20 30.
• Hàm find(value) trả về một iterator tới lần xuất hiện đầu tiên của value trong multiset (theo thứ tự sắp xếp). Nếu không tìm thấy, nó trả về myMultiset.end().
• Hàm count(value) là điểm mấu chốt cho bài toán đếm tần suất! Nó trả về số lần xuất hiện của value trong multiset. Độ phức tạp của count trên std::multiset là O(log n + k) nơi k là số lần xuất hiện của phần tử, nhưng thường được coi là O(log n) trong thực tế nếu k nhỏ hoặc nếu phần tử không xuất hiện.
• Hàm erase() có hai dạng:
  • erase(iterator): Xóa phần tử mà iterator đó trỏ tới. Đây là cách để xóa chỉ một lần xuất hiện của một phần tử.
  • erase(value): Xóa tất cả các lần xuất hiện của value trong multiset.

Như vậy, std::multiset là một cấu trúc tiện lợi khi bạn cần lưu trữ một bộ sưu tập có thể chứa các phần tử lặp lại và muốn dễ dàng thao tác (thêm, xóa, tìm kiếm, đếm) với chúng theo thứ tự.

Bài toán đếm tần suất (Frequency Counting)

Đây là bài toán kinh điển: Cho một danh sách các phần tử, hãy đếm xem mỗi phần tử xuất hiện bao nhiêu lần. Ví dụ:

• Danh sách số: [1, 5, 2, 1, 5, 1, 3]
  • Kết quả: 1 xuất hiện 3 lần, 5 xuất hiện 2 lần, 2 xuất hiện 1 lần, 3 xuất hiện 1 lần.
• Chuỗi ký tự: "programming is fun"
  • Kết quả: 'p' 1 lần, 'r' 2 lần, 'o' 1 lần, 'g' 2 lần, 'a' 1 lần, 'm' 2 lần, 'i' 2 lần, 's' 1 lần, ' ' 2 lần, 'f' 1 lần, 'u' 1 lần, 'n' 1 lần.

Có nhiều cách để giải bài toán này:

1. Sử dụng mảng/vector và sắp xếp: Sắp xếp danh sách, sau đó duyệt qua danh sách đã sắp xếp để đếm các nhóm phần tử giống nhau liên tiếp. Cách này hiệu quả nếu bạn chỉ cần in ra tần suất hoặc xử lý theo thứ tự, nhưng việc sắp xếp ban đầu có thể tốn kém (O(N log N)).

2. Sử dụng mảng băm (hash map) hoặc cây nhị phân tìm kiếm (map): Đây là cách phổ biến và hiệu quả nhất. Chúng ta dùng std::map hoặc std::unordered_map để lưu trữ cặp (phần tử, tần suất). Khi duyệt qua danh sách gốc, với mỗi phần tử, ta tăng giá trị tần suất tương ứng trong map.

   • std::map: Dữ liệu được lưu trữ theo thứ tự của khóa. Độ phức tạp trung bình O(log N) cho mỗi thao tác thêm/cập nhật.
   • std::unordered_map: Dữ liệu không được sắp xếp. Độ phức tạp trung bình O(1) cho mỗi thao tác thêm/cập nhật (trong trường hợp tốt nhất/trung bình), nhưng có thể O(N) trong trường hợp xấu nhất (va chạm hàm băm).

3. Sử dụng Multiset: Đây là nơi Multiset thể hiện vai trò của mình. Chúng ta chỉ cần thêm tất cả các phần tử từ danh sách gốc vào multiset. Sau đó, để biết tần suất của một phần tử bất kỳ, ta chỉ việc gọi phương thức count() của multiset.

Hãy xem xét các ví dụ minh họa cho cách 2 và cách 3.

Ví dụ 1: Đếm tần suất sử dụng std::map

Bài toán: Đếm tần suất xuất hiện của các số trong một vector.

#include <iostream>
#include <vector>
#include <map>    // Include header cho map

int main() {
    std::vector<int> numbers = {1, 5, 2, 1, 5, 1, 3, 2, 4, 4, 5, 1};

    // Sử dụng std::map để lưu trữ (so -> tan_suat)
    std::map<int, int> frequencyMap;

    // Duyet qua vector va cap nhat tan suat trong map
    std::cout << "Dang dem tan suat..." << std::endl;
    for (int number : numbers) {
        frequencyMap[number]++; // Nếu number chưa có trong map, nó sẽ được thêm vào với giá trị mặc định là 0, sau đó tăng lên 1.
                                // Nếu number đã có, giá trị tần suất của nó sẽ được tăng lên 1.
    }

    // In ra ket qua
    std::cout << "\nKet qua dem tan suat (su dung std::map):" << std::endl;
    // map luu tru cac phan tu theo thu tu key (so)
    for (const auto& pair : frequencyMap) {
        std::cout << "So " << pair.first << " xuat hien " << pair.second << " lan." << std::endl;
    }
    /* Output se tuong tu:
    So 1 xuat hien 4 lan.
    So 2 xuat hien 2 lan.
    So 3 xuat hien 1 lan.
    So 4 xuat hien 2 lan.
    So 5 xuat hien 3 lan.
    */

    return 0;
}

Giải thích code:

• Chúng ta khai báo một std::map<int, int> có tên frequencyMap. Key của map là số cần đếm, và Value là tần suất của số đó.
• Duyệt qua vector numbers. Với mỗi số number, chúng ta truy cập vào frequencyMap[number].
• Phép toán [] trên map có tính năng đặc biệt: nếu key number chưa tồn tại trong map, nó sẽ tự động tạo một entry mới với key là number và value được khởi tạo mặc định (0 cho kiểu int). Sau đó, toán tử ++ sẽ tăng giá trị này lên 1.
• Nếu key number đã tồn tại, toán tử [] sẽ trả về tham chiếu tới value hiện tại, và toán tử ++ sẽ tăng giá trị đó lên 1.
• Cuối cùng, chúng ta duyệt qua frequencyMap. Vì std::map lưu trữ theo thứ tự key, kết quả in ra cũng theo thứ tự của các số.

std::map (hoặc std::unordered_map nếu không cần giữ thứ tự và muốn hiệu năng trung bình tốt hơn) là cách tiếp cận rất phổ biến và hiệu quả cho bài toán đếm tần suất khi bạn chỉ cần biết mỗi phần tử duy nhất xuất hiện bao nhiêu lần.

Ví dụ 2: Đếm tần suất sử dụng std::multiset

Bây giờ, hãy xem cách dùng std::multiset cho cùng bài toán.

#include <iostream>
#include <vector>
#include <set>    // Include header cho multiset

int main() {
    std::vector<int> numbers = {1, 5, 2, 1, 5, 1, 3, 2, 4, 4, 5, 1};

    // Sử dụng std::multiset để luu tru tat ca cac so, bao gom ca so lap lai
    std::multiset<int> myMultiset;

    // Them tat ca cac so tu vector vao multiset
    std::cout << "Them cac so vao multiset..." << std::endl;
    for (int number : numbers) {
        myMultiset.insert(number);
    }

    // De biet tan suat, ta dung phuong thuc count()
    std::cout << "\nKet qua dem tan suat (su dung std::multiset va count()):" << std::endl;

    // Van de o day la lam the nao de biet cac *phan tu duy nhat* co trong multiset
    // Ta co the copy cac phan tu duy nhat vao mot set hoac vector rieng de duyet
    // Hoac chi can hoi tan suat cua cac so ma ta quan tam

    // Vi du: Chi hoi tan suat cua mot vai so cu the
    std::cout << "So 1 xuat hien " << myMultiset.count(1) << " lan." << std::endl; // Output: 4
    std::cout << "So 5 xuat hien " << myMultiset.count(5) << " lan." << std::endl; // Output: 3
    std::cout << "So 9 xuat hien " << myMultiset.count(9) << " lan." << std::endl; // Output: 0

    // Neu muon liet ke tan suat cua tat ca *cac so duy nhat* co trong multiset:
    // Ta can mot cach de lay ra cac so duy nhat. Mot cach la copy vao mot std::set
    std::set<int> uniqueNumbers(myMultiset.begin(), myMultiset.end());

    std::cout << "\nLiet ke tan suat cua tat ca cac so duy nhat:" << std::endl;
    for (int uniqueNum : uniqueNumbers) {
         std::cout << "So " << uniqueNum << " xuat hien " << myMultiset.count(uniqueNum) << " lan." << std::endl;
    }
    /* Output se tuong tu:
    So 1 xuat hien 4 lan.
    So 2 xuat hien 2 lan.
    So 3 xuat hien 1 lan.
    So 4 xuat hien 2 lan.
    So 5 xuat hien 3 lan.
    */


    return 0;
}

Giải thích code:

• Chúng ta khai báo một std::multiset<int> có tên myMultiset.
• Duyệt qua vector numbers và thêm tất cả các phần tử vào myMultiset bằng insert(). Multiset bây giờ chứa {1, 1, 1, 1, 2, 2, 3, 4, 4, 5, 5, 5} (theo thứ tự sắp xếp).
• Để biết tần suất của một số cụ thể (ví dụ số 1), chúng ta gọi myMultiset.count(1). Hàm này sẽ duyệt qua multiset và trả về số lần nó tìm thấy số 1.
• Điểm khác biệt quan trọng: Multiset không tự động cung cấp một danh sách các phần tử duy nhất cùng với tần suất của chúng như map làm. Nếu bạn muốn in ra tần suất của tất cả các phần tử duy nhất có trong multiset, bạn cần thêm một bước phụ. Một cách đơn giản là tạo một std::set mới từ các phần tử của multiset (vì std::set chỉ lưu các phần tử duy nhất). Sau đó, duyệt qua set này và với mỗi phần tử duy nhất, dùng myMultiset.count() để lấy tần suất của nó từ multiset ban đầu.

Khi nào nên dùng Multiset cho bài toán đếm tần suất?

Mặc dù std::map (hoặc unordered_map) thường là lựa chọn hiệu quả hơn và trực tiếp hơn cho chỉ việc đếm tần suất của các phần tử duy nhất, std::multiset vẫn có những trường hợp sử dụng riêng và ưu điểm của nó:

• Khi bạn cần lưu trữ toàn bộ bộ sưu tập ban đầu, bao gồm cả các phần tử lặp lại, VÀ thỉnh thoảng cần truy vấn tần suất: Multiset lưu trữ đầy đủ dữ liệu gốc, trong khi map chỉ lưu trữ các phần tử duy nhất và tần suất của chúng.
• Khi bạn cần thực hiện các thao tác khác trên bộ sưu tập có chứa phần tử lặp lại một cách hiệu quả theo thứ tự: Ví dụ: tìm phần tử lớn nhất/nhỏ nhất (đầu/cuối multiset), tìm phần tử thứ k (với các kỹ thuật bổ sung trên cây), hoặc xóa một lần xuất hiện của một phần tử. Multiset cung cấp các iterator cho phép duyệt và xóa các phần tử cụ thể theo thứ tự.
• Khi tính năng sắp xếp tự động là quan trọng: std::multiset giữ các phần tử theo thứ tự.

So sánh tóm tắt:

Trong hầu hết các bài toán chỉ yêu cầu đếm tần suất và in ra kết quả, std::map hoặc std::unordered_map là lựa chọn tối ưu hơn. Tuy nhiên, nếu bài toán phức tạp hơn đòi hỏi cả việc lưu trữ đầy đủ dữ liệu gốc và các thao tác dựa trên tần suất và thứ tự, std::multiset có thể là công cụ phù hợp.

Ví dụ 3: Sử dụng Multiset trong bài toán kết hợp lưu trữ và đếm

Hãy xem một bài toán giả định: Bạn có một danh sách các điểm số của học sinh. Bạn muốn lưu trữ tất cả các điểm số này và sau đó muốn biết có bao nhiêu học sinh đạt điểm A (ví dụ >= 90), bao nhiêu học sinh đạt điểm B (>=80), v.v... đồng thời bạn cũng có thể muốn xóa một điểm số cụ thể của một học sinh nào đó.

#include <iostream>
#include <vector>
#include <set> // std::multiset

int main() {
    std::vector<int> scores = {85, 92, 78, 95, 88, 92, 76, 90, 85, 98, 88, 78};

    // Sử dụng multiset để lưu trữ tat ca diem so
    std::multiset<int> studentScores;

    std::cout << "Them diem so vao multiset..." << std::endl;
    for (int score : scores) {
        studentScores.insert(score);
    }

    // Diem so da duoc sap xep trong multiset
    std::cout << "Cac diem so (da sap xep): ";
    for (int score : studentScores) {
        std::cout << score << " ";
    }
    std::cout << std::endl; // Output: 76 78 78 85 85 88 88 90 92 92 95 98

    // Bai toan: Dem so hoc sinh dat diem A (>= 90)
    // Trong multiset da sap xep, cac diem >= 90 se nam tu mot diem nao do den het
    // std::multiset::lower_bound(value) tra ve iterator toi phan tu DAU TIEN >= value
    auto it_A = studentScores.lower_bound(90);

    // So luong phan tu tu it_A den end() chinh la so hoc sinh dat diem >= 90
    // Cach 1: Duyet tu it_A den end() va dem (khong hieu qua)
    // Cach 2: Su dung std::distance (hieu qua)
    int countA = std::distance(it_A, studentScores.end());
    std::cout << "So hoc sinh dat diem A (>= 90): " << countA << std::endl; // Output: 5

    // Bai toan: Dem so hoc sinh dat diem B (>= 80 va < 90)
    // Diem B se nam tu >= 80 den < 90
    auto it_B_start = studentScores.lower_bound(80); // Iterator toi phan tu >= 80 dau tien
    auto it_B_end = studentScores.lower_bound(90);   // Iterator toi phan tu >= 90 dau tien (hay < 90 cuoi cung + 1)

    // So luong phan tu tu it_B_start den it_B_end la so hoc sinh dat diem >= 80 va < 90
    int countB = std::distance(it_B_start, it_B_end);
    std::cout << "So hoc sinh dat diem B (>= 80 va < 90): " << countB << std::endl; // Output: 5

    // Bai toan: Diem bao nhieu lan xuat hien cua mot diem cu the (vi du diem 85)
    std::cout << "So hoc sinh dat diem 85: " << studentScores.count(85) << " lan." << std::endl; // Output: 2

    // Bai toan: Mot hoc sinh co diem 88 da duoc cham lai va tang len 90. Xoa mot lan 88 va them mot lan 90.
    auto it_to_erase = studentScores.find(88); // Tim mot lan xuat hien cua 88
    if (it_to_erase != studentScores.end()) {
        studentScores.erase(it_to_erase); // Xoa lan xuat hien do
        studentScores.insert(90);         // Them diem moi
        std::cout << "\nCap nhat diem: mot hoc sinh tu 88 len 90." << std::endl;
    }

    // Kiem tra lai sau khi cap nhat
    std::cout << "So hoc sinh dat diem 88 sau cap nhat: " << studentScores.count(88) << std::endl; // Output: 1
    std::cout << "So hoc sinh dat diem 90 sau cap nhat: " << studentScores.count(90) << " lan." << std::endl; // Output: 2 (vi ban dau co 1 hoc sinh 90, them 1 nua)
    std::cout << "So hoc sinh dat diem A (>= 90) sau cap nhat: " << std::distance(studentScores.lower_bound(90), studentScores.end()) << std::endl; // Output: 6

    return 0;
}

Giải thích code:

• Chúng ta dùng std::multiset để lưu trữ tất cả các điểm số, giữ nguyên các điểm lặp lại. Nhờ đặc tính của std::multiset, các điểm số tự động được sắp xếp.
• Để đếm số học sinh đạt điểm A (>= 90), chúng ta sử dụng studentScores.lower_bound(90). Phương thức này trả về một iterator trỏ tới phần tử đầu tiên trong multiset có giá trị lớn hơn hoặc bằng 90. Vì multiset đã được sắp xếp, tất cả các điểm >= 90 sẽ nằm từ vị trí này đến cuối multiset.
• Hàm std::distance(iterator1, iterator2) (cần #include <iterator>) tính khoảng cách giữa hai iterator, tức là số lượng phần tử trong khoảng đó. Chúng ta dùng nó để đếm số phần tử từ lower_bound(90) đến studentScores.end().
• Tương tự, để đếm điểm B (>= 80 và < 90), chúng ta tìm lower_bound(80) (bắt đầu) và lower_bound(90) (kết thúc của khoảng điểm B).
• Chúng ta vẫn có thể dùng count(value) để đếm tần suất của một điểm cụ thể (ví dụ 85).
• Trong phần cập nhật điểm, chúng ta thấy ưu điểm của multiset khi cần thao tác trên từng phiên bản của phần tử. Chúng ta dùng find(88) để lấy iterator tới một trong những lần xuất hiện của điểm 88, sau đó dùng erase(iterator) để xóa chỉ một điểm 88 đó, rồi thêm điểm mới là 90. Nếu dùng map, việc này sẽ phức tạp hơn vì map chỉ lưu trữ số lượng chứ không lưu trữ từng bản sao.

Ví dụ này cho thấy std::multiset không chỉ hữu ích cho việc đếm tần suất cơ bản qua count(), mà còn kết hợp tốt với các tính năng khác (như sắp xếp và các phương thức tìm kiếm dựa trên thứ tự như lower_bound) cho các bài toán phức tạp hơn liên quan đến tập hợp có phần tử lặp lại.

Bài tập ví dụ:

Độ dài tối thiểu

Trong một chuyến đi bằng tàu hỏa, FullHouse Dev đang nghiên cứu về cách sắp xếp các toa tàu. Họ nhận thấy có hai đoàn tàu cần được sắp xếp sao cho giống nhau. Với kinh nghiệm trong việc tối ưu hóa, họ quyết định tìm cách di chuyển ít toa tàu nhất có thể để đạt được mục tiêu này.

Bài toán

FullHouse Dev có hai mảng \(A\) và \(B\) có độ dài \(n\). Họ có thể chọn bất kỳ đoạn con nào và sắp xếp các phần tử trong đoạn con đó theo thứ tự tăng dần cho cả hai mảng. Nhiệm vụ của họ là tìm ra độ dài ngắn nhất của đoạn con để sau khi sắp xếp, mảng \(A\) và \(B\) sẽ trở nên giống nhau. Hai mảng \(A\) và \(B\) là các hoán vị của nhau.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
• Dòng đầu tiên của mỗi test case chứa số nguyên \(n\)
• Dòng tiếp theo chứa \(n\) số nguyên - các phần tử của mảng \(A\)
• Dòng cuối cùng chứa \(n\) số nguyên - các phần tử của mảng \(B\)

OUTPUT FORMAT:

Với mỗi test case, in ra độ dài tối thiểu của đoạn con cần chọn để làm cho \(A\) và \(B\) giống nhau sau khi sắp xếp.

Ràng buộc:

• \(1 \leq T \leq 100\)
• \(1 \leq n \leq 10^5\)
• \(1 \leq A[i], B[i] \leq 10^9\)

Ví dụ

INPUT

2
3
2 3 1
2 1 3
4
1 1 2 1
2 1 1 1

OUTPUT

2
3

Giải thích

• Test case 1: FullHouse Dev có thể chọn đoạn toa tàu từ vị trí 1 đến 2 (tính từ 1). Sau khi sắp xếp lại các toa tàu trong đoạn này, hai đoàn tàu sẽ giống nhau. Do đó đáp án là 2.
• Test case 2: Nhóm cần chọn đoạn toa tàu từ vị trí 2 đến 4. Sau khi sắp xếp lại các toa tàu trong đoạn này, hai đoàn tàu sẽ trở nên giống nhau. Vì vậy đáp án là 3. Tuyệt vời! Bài toán này là một ứng dụng hay của việc phân tích sự khác biệt giữa hai mảng. Dưới đây là hướng dẫn giải ngắn gọn bằng C++:

1. Phân tích bài toán:

   • Ta có hai mảng A và B là hoán vị của nhau.
   • Ta chọn cùng một đoạn con [l, r] trên cả hai mảng và sắp xếp nó.
   • Mục tiêu: Tìm độ dài r - l + 1 nhỏ nhất sao cho sau khi sắp xếp đoạn [l, r], hai mảng A và B trở nên giống hệt nhau.

2. Điều kiện để hai mảng giống nhau sau khi sắp xếp đoạn [l, r]:

   • Các phần tử ngoài đoạn [l, r] không bị thay đổi. Do đó, để mảng cuối cùng giống nhau, các phần tử A[i] và B[i] phải bằng nhau cho mọi i < l hoặc i > r ngay từ đầu.
   • Các phần tử trong đoạn [l, r] sau khi sắp xếp phải giống nhau. Vì A và B là hoán vị của nhau, và các phần tử ngoài đoạn [l, r] đã khớp, điều này đảm bảo rằng tập hợp các phần tử (multiset) trong đoạn A[l...r] và B[l...r] ban đầu là như nhau. Do đó, khi sắp xếp cả hai đoạn này, chúng sẽ trở nên giống hệt nhau.
   • Kết luận: Để hai mảng trở nên giống nhau sau khi sắp xếp đoạn [l, r], đoạn con này phải chứa tất cả các vị trí mà A[i] khác B[i] ban đầu.

3. Tìm đoạn con ngắn nhất:

   • Để đoạn con [l, r] chứa tất cả các vị trí khác nhau và có độ dài r - l + 1 nhỏ nhất, l phải là chỉ số khác nhau đầu tiên (nhỏ nhất) và r phải là chỉ số khác nhau cuối cùng (lớn nhất).

4. Thuật toán:

   • Bước 1: Duyệt từ đầu mảng (chỉ số 0) để tìm chỉ số l đầu tiên mà A[l] != B[l].
   • Bước 2: Nếu không tìm thấy chỉ số l nào (tức là A và B đã giống hệt nhau), thì độ dài tối thiểu là 0.
   • Bước 3: Nếu tìm thấy l, duyệt từ cuối mảng (chỉ số n-1) để tìm chỉ số r đầu tiên (tính từ cuối) mà A[r] != B[r]. Đây chính là chỉ số khác nhau cuối cùng.
   • Bước 4: Độ dài tối thiểu của đoạn con cần sắp xếp là r - l + 1.

Ví dụ 1 áp dụng thuật toán: A = [2, 3, 1], B = [2, 1, 3]

• Tìm l: A[0]=B[0], A[1]!=B[1]. l = 1.
• Tìm r: A[2]!=B[2]. r = 2.
• Độ dài = r - l + 1 = 2 - 1 + 1 = 2.

Ví dụ 2 áp dụng thuật toán: A = [1, 1, 2, 1], B = [2, 1, 1, 1]

• Tìm l: A[0]!=B[0]. l = 0.
• Tìm r: A[3]=B[3], A[2]!=B[2]. r = 2.
• Độ dài = r - l + 1 = 2 - 0 + 1 = 3.

Lưu ý khi cài đặt: Sử dụng vector trong C++ để lưu trữ mảng. Đọc đầu vào theo định dạng đã cho. Cẩn thận với chỉ số mảng (0-indexed trong C++ so với 1-indexed trong ví dụ giải thích).

Làm thêm nhiều bài tập miễn phí tại đây