Trang chủ Bài tập Kỳ thi Bài nộp Xếp hạng Thảo luận Trợ giúp
Đăng nhập Đăng ký
Thảo luận
Khu vực thảo luận

CHUYÊN ĐỀ SẮP XẾP NHANH VÀ TÌM KIẾM NHỊ PHÂN

Trùm CUỐI 2025-06-24 12:17:07 2025-06-24 12:19:30

Mục tiêu:

  • Hiểu rõ nguyên lý hoạt động và ưu/nhược điểm của các thuật toán sắp xếp O(N \log N) .
  • Sử dụng thành thạo std::sort với hàm so sánh tùy chỉnh.
  • Nắm vững và cài đặt chính xác Tìm kiếm nhị phân trên mảng, bao gồm các biến thể lower_bound và upper_bound.
  • Làm chủ kỹ thuật tư duy "Tìm kiếm nhị phân trên kết quả" để giải quyết các bài toán tối ưu hóa.

Lời Mở Đầu

Trong thế giới rộng lớn của khoa học máy tính, có hai thao tác cơ bản nhưng lại xuất hiện với tần suất đáng kinh ngạc: Sắp xếp (Sorting) và Tìm kiếm (Searching). Từ việc quản lý danh bạ điện thoại, hiển thị bảng xếp hạng trong một trò chơi, cho đến cách các công cụ tìm kiếm khổng lồ như Google xử lý hàng tỷ trang web, tất cả đều quy về việc tổ chức và truy xuất dữ liệu một cách hiệu quả.

Hãy tưởng tượng bạn đang cần tìm một từ trong một cuốn từ điển. Nếu các từ được xếp lộn xộn, bạn sẽ phải lật từng trang một, một công việc tẻ nhạt và mất thời gian. Nhưng vì từ điển đã được sắp xếp theo thứ tự bảng chữ cái, bạn có thể nhanh chóng mở đến đúng khu vực và tìm thấy từ mình cần trong vài giây.

Đây chính là sức mạnh của trật tự. Một mảng dữ liệu đã được sắp xếp mở ra vô số khả năng để tối ưu hóa thuật toán. Nó cho phép chúng ta thực hiện các phép toán tìm kiếm, thống kê, và xử lý dữ liệu với tốc độ không tưởng so với việc làm việc trên dữ liệu thô, chưa được tổ chức.

Chuyên đề này sẽ giải quyết hai câu hỏi cốt lõi:

  1. Làm thế nào để sắp xếp một tập hợp dữ liệu một cách hiệu quả nhất?
  2. Sau khi đã có trật tự, làm thế nào để tận dụng nó để tìm kiếm thông tin một cách nhanh chóng và chính xác?

Chúng ta sẽ cùng nhau khám phá từ những thuật toán kinh điển, học cách sử dụng các công cụ mạnh mẽ có sẵn trong ngôn ngữ lập trình, và làm chủ một kỹ thuật tư duy đỉnh cao để giải quyết các bài toán tối ưu phức tạp. Hãy bắt đầu hành trình xây dựng nền tảng hiệu quả cho mọi thuật toán của bạn!

Phần I: Nghệ Thuật Sắp Xếp (Sorting)

Mục tiêu: Hiểu bản chất các thuật toán sắp xếp hiệu quả và sử dụng công cụ có sẵn một cách linh hoạt.

A. Tại Sao Cần O(N log N)?

Khi mới bắt đầu học lập trình, chúng ta thường được giới thiệu các thuật toán sắp xếp đơn giản, dễ hiểu. Tuy nhiên, sự đơn giản này phải trả một cái giá đắt về mặt hiệu năng.

1. Ôn lại các thuật toán O(N^2)

Đây là những thuật toán sắp xếp cơ bản, hoạt động dựa trên các vòng lặp lồng nhau để so sánh và đổi chỗ các phần tử.

  • Selection Sort (Sắp xếp chọn):
    • Ý tưởng: Ở mỗi bước, tìm phần tử nhỏ nhất trong đoạn chưa được sắp xếp và đưa nó về đầu đoạn.
  • Insertion Sort (Sắp xếp chèn):
    • Ý tưởng: Với mỗi phần tử, chèn nó vào đúng vị trí trong dãy đã được sắp xếp đứng trước nó.
  • Bubble Sort (Sắp xếp nổi bọt):
    • Ý tưởng: Lặp đi lặp lại việc so sánh hai phần tử kế cận và đổi chỗ nếu chúng sai thứ tự, đưa phần tử lớn nhất "nổi" dần về cuối mảng.

Phân tích: Các thuật toán này trực quan, dễ cài đặt nhưng có độ phức tạp thời gian là O(N^2) .

  • Với N = 5,000 , số thao tác là 25,000,000 (bắt đầu chậm).
  • Với N = 100,000 , số thao tác là 10,000,000,000 (quá lớn, chắc chắn gây "Time Limit Exceeded").

Do đó, các thuật toán O(N^2) chỉ hiệu quả với N rất nhỏ ( N \le 5000 ). Để xử lý dữ liệu lớn, chúng ta cần các thuật toán O(N \log N) .

2. Sức mạnh của std::sort trong C++

Trong 99% trường hợp thi đấu và ứng dụng, hãy dùng std::sort.

std::sort là một triển khai được tối ưu hóa cao (thường là Introsort), có độ phức tạp trung bình và xấu đều là O(N \log N) .

  • Cú pháp cơ bản:

    #include <vector>
#include <algorithm>

std::vector<int> arr = {5, 2, 8, 1, 9, 4};
// Sắp xếp tăng dần
std::sort(arr.begin(), arr.end());

  • Hàm so sánh tùy chỉnh (Custom Comparator): Đây là lúc std::sort thể hiện sức mạnh linh hoạt. Ta có thể định nghĩa tiêu chí sắp xếp riêng.

    Ví dụ: Sắp xếp một mảng các Student theo điểm giảm dần, nếu điểm bằng nhau thì theo tên tăng dần.

    struct Student {
    std::string name;
    int score;
};

    Cách 1: Dùng hàm bool compare(a, b) Hàm trả về true nếu a nên đứng trước b.

    bool compareStudents(const Student& a, const Student& b) {
    if (a.score != b.score) {
        return a.score > b.score; // Điểm cao hơn đứng trước
    }
    return a.name < b.name; // Tên theo thứ tự từ điển
}

// Sử dụng:
// std::sort(students.begin(), students.end(), compareStudents);

    Cách 2: Dùng Lambda expression (Hiện đại và tiện lợi) Viết comparator ngay trong lời gọi hàm sort.

    // std::vector<Student> students = ...;
std::sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
    if (a.score != b.score) {
        return a.score > b.score;
    }
    return a.name < b.name;
});

B. Tìm Hiểu Sâu Hơn: Các Thuật Toán O(N log N) Kinh Điển

1. Merge Sort (Sắp xếp trộn)

  • Tư tưởng: Chia để trị (Divide and Conquer).
  • Các bước:
    1. Chia (Divide): Chia mảng thành 2 nửa.
    2. Trị (Conquer): Gọi đệ quy sắp xếp 2 nửa này.
    3. Kết hợp (Combine/Merge): Trộn 2 mảng con đã sắp xếp thành 1 mảng lớn được sắp xếp. Đây là bước quan trọng nhất.
  • Minh họa trực quan:
    [8, 3, 5, 1, 9, 4, 2, 7]
      /               \
[8, 3, 5, 1]       [9, 4, 2, 7]
   /      \           /      \
[8, 3]  [5, 1]     [9, 4]  [2, 7] -> Chia đến khi còn 1 phần tử
/   \   /   \     /   \   /   \
[8] [3] [5] [1]   [9] [4] [2] [7]
---------------------------------- -> Bắt đầu trộn
[3, 8]  [1, 5]     [4, 9]  [2, 7]
   \      /           \      /
[1, 3, 5, 8]       [2, 4, 7, 9]
      \               /
   [1, 2, 3, 4, 5, 7, 8, 9]
  • Phân tích:
    • Độ phức tạp thời gian: Luôn là O(N \log N) .
    • Độ phức tạp không gian: O(N) do cần mảng phụ để trộn.
    • Tính chất: Là thuật toán sắp xếp ổn định (Stable Sort), giữ nguyên thứ tự tương đối của các phần tử bằng nhau.
  • Ứng dụng đặc biệt: Đếm cặp nghịch thế (Counting Inversions) Một cặp nghịch thế là một cặp chỉ số (i, j) sao cho i < j và A[i] > A[j] . Merge Sort có thể đếm số cặp nghịch thế trong O(N \log N) . Ý tưởng là khi trộn 2 mảng con L và R, nếu ta lấy 1 phần tử từ R đưa vào mảng kết quả, thì nó nhỏ hơn tất cả các phần tử còn lại trong L. Ta cộng số phần tử còn lại đó vào tổng số nghịch thế.

2. Heap Sort (Sắp xếp vun đống)

  • Kiến thức tiên quyết: Cấu trúc dữ liệu Heap (thường là Max-Heap). std::priority_queue trong C++ là một ví dụ về Heap.
  • Tư tưởng:
    1. Xây dựng Heap: Biến mảng ban đầu thành một Max-Heap. Phần tử lớn nhất sẽ ở gốc.
    2. Sắp xếp: Lặp lại N-1 lần:
      • Đưa phần tử lớn nhất (ở gốc Heap) về đúng vị trí cuối mảng (bằng cách hoán đổi với phần tử cuối).
      • Loại phần tử đó ra khỏi Heap (giảm kích thước heap đi 1) và hiệu chỉnh lại Heap (vun lại đống).
  • Phân tích:
    • Độ phức tạp thời gian: O(N \log N) .
    • Độ phức tạp không gian: O(1) (sắp xếp tại chỗ - in-place).
    • Tính chất: Không ổn định (Unstable).

Phần II: Tìm Kiếm Nhị Phân (Binary Search) – Chia Để Tìm

Mục tiêu: Nắm vững công cụ tìm kiếm mạnh mẽ nhất trên dữ liệu đã có thứ tự.

A. Tìm Kiếm Nhị Phân trên Mảng

1. Điều kiện tiên quyết: Mảng phải được sắp xếp.

2. Tư tưởng: Tại mỗi bước, so sánh phần tử cần tìm với phần tử ở giữa, loại bỏ đi một nửa không gian tìm kiếm. Quá trình này lặp lại cho đến khi tìm thấy phần tử hoặc không gian tìm kiếm rỗng. Độ phức tạp là O(\log N) .

3. Code Template:

// Trả về chỉ số của target nếu tìm thấy, ngược lại trả về -1
int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        // Lưu ý quan trọng: Cách tính mid để tránh tràn số
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // Tìm thấy
        } else if (arr[mid] < target) {
            left = mid + 1; // Tìm ở nửa bên phải
        } else {
            right = mid - 1; // Tìm ở nửa bên trái
        }
    }
    return -1; // Không tìm thấy
}

4. Các biến thể trong C++ (<algorithm>)

  • binary_search(): Trả về true/false. Dùng để kiểm tra sự tồn tại.
  • lower_bound(): Trả về iterator đến phần tử đầu tiên không nhỏ hơn giá trị tìm kiếm ( \ge val ).
  • upper_bound(): Trả về iterator đến phần tử đầu tiên lớn hơn giá trị tìm kiếm ( > val ).

Ứng dụng: Đếm số lần xuất hiện của một phần tử k bằng upper_bound - lower_bound.

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> data = {1, 2, 4, 4, 4, 4, 7, 9, 9};

    // Tìm con trỏ tới vị trí đầu tiên >= 4
    auto first = std::lower_bound(data.begin(), data.end(), 4);

    // Tìm con trỏ tới vị trí đầu tiên > 4
    auto last = std::upper_bound(data.begin(), data.end(), 4);

    // Khoảng cách giữa hai con trỏ là số lượng phần tử
    int count = std::distance(first, last);

    std::cout << "So lan xuat hien cua so 4 la: " << count << std::endl; // In ra: 4
}

Phần III: Tuyệt Kỹ: Tìm Kiếm Nhị Phân trên Kết Quả (Binary Search the Answer)

Mục tiêu: Trang bị một phương pháp tư duy mạnh mẽ để giải quyết lớp bài toán tối ưu.

A. Sự Thay Đổi trong Tư Duy

Chúng ta chuyển từ "tìm một giá trị trong mảng" sang "tìm câu trả lời tối ưu trong một khoảng".

Dấu hiệu nhận biết:

  • Bài toán yêu cầu tìm giá trị nhỏ nhất thoả mãn một điều kiện, hoặc lớn nhất thoả mãn một điều kiện.
  • Tồn tại tính đơn điệu (monotonicity) của hàm kiểm tra.

B. "Hàm Kiểm Tra" - Trái Tim của Thuật Toán

  • Định nghĩa hàm check(x): Một hàm boolean trả về true nếu "kết quả x có thể đạt được" và false nếu không.
  • Tính đơn điệu:
    • Nếu tìm min và check(x) là true, thì mọi y > x cũng làm check(y) là true. (Dạng: F F F T T T)
    • Nếu tìm max và check(x) là true, thì mọi y < x cũng làm check(y) là true. (Dạng: T T T F F F)
  • Mục tiêu: Tìm ra ranh giới giữa true và false.

C. Khuôn Mẫu (Framework) Giải Bài Toán

  1. Xác định không gian tìm kiếm của kết quả: Tìm low và high hợp lý cho đáp án.

  2. Viết hàm check(mid): Đây là phần khó nhất, thường là một thuật toán tham lam, duyệt, hoặc kỹ thuật khác.

  3. Vòng lặp tìm kiếm nhị phân:

    // Ví dụ tìm giá trị nhỏ nhất thỏa mãn (dạng F...FT...T)
long long low = min_possible_ans, high = max_possible_ans;
long long ans = high; // Hoặc một giá trị khởi tạo phù hợp

while (low <= high) {
    long long mid = low + (high - low) / 2;
    if (check(mid)) { // Nếu mid khả thi, thử tìm kết quả nhỏ hơn nữa
        ans = mid;
        high = mid - 1;
    } else { // Nếu mid không khả thi, phải tăng giá trị lên
        low = mid + 1;
    }
}
// ans là kết quả

D. Các Ví dụ Kinh Điển

1. Aggressive Cows (VNOI/SPOJ)

  • Bài toán: Tìm khoảng cách lớn nhất có thể giữa 2 con bò sao cho đặt được K con bò vào N chuồng.
  • Tìm kiếm: Khoảng cách D.
  • Hàm check(D): Có thể đặt được K con bò với khoảng cách tối thiểu là D không?
  • Giải check(D) (Tham lam): Sắp xếp vị trí chuồng. Đặt con bò đầu tiên ở chuồng 1. Với mỗi con bò tiếp theo, đặt nó vào chuồng sớm nhất có thể mà vẫn đảm bảo khoảng cách ≥ D so với con bò trước đó. Đếm xem có đặt đủ K con không.

2. Cutting Wood / EKO (SPOJ)

  • Bài toán: Tìm chiều cao H lớn nhất để cắt cây sao cho tổng số gỗ thu được ít nhất là M.
  • Tìm kiếm: Chiều cao H.
  • Hàm check(H): Nếu cắt ở độ cao H, tổng gỗ thu được có lớn hơn hoặc bằng M không?
  • Giải check(H) (Duyệt): Duyệt qua mảng các cây, với mỗi cây cao c > H, cộng c - H vào tổng. So sánh tổng với M.

Phần IV: Bài Tập Luyện Tập

Nhóm 1: Sắp xếp

Nhóm 2: Tìm kiếm nhị phân trên mảng

  • Sum of Two Values (CSES): https://cses.fi/problemset/task/1640
    • Gợi ý: Sắp xếp mảng, với mỗi phần tử a[i], dùng tìm kiếm nhị phân để tìm X - a[i].
  • Where is the Marble? (VNOI - UVA 10474): https://oj.vnoi.info/problem/uva10474
    • Gợi ý: Bài tập cơ bản để luyện tập tìm vị trí phần tử đầu tiên, rất phù hợp với lower_bound.

Nhóm 3: Tìm kiếm nhị phân trên kết quả

Chuyên Sơn La Online Judge.
Mã nguồn mở cho giải pháp chấm bài trực tuyến (Online Judge): DMOJ - UOJ - QDUOJ - SYZOJ - OJS - SHARIF - AURORA - CMS