Chương 05

Tuyển Tập Bóc Tách
Bài Toán Ứng Dụng Thực Tế

Mỗi bài toán dưới đây đều có bước phân tích từ đề bài → nhận diện thuật toán → code giải → giải thích chi tiết. Nhấn vào tiêu đề để mở rộng.

🃏 Bài 1 — Card Night

📋 Đề bài tóm tắt

Bạn đang cầm các lá bài đã sắp xếp. Khi nhận thêm một lá bài mới, hãy chèn nó vào đúng vị trí để tay bài vẫn được sắp xếp. In ra mảng bài sau mỗi lần chèn.

🔍 Nhận diện

Dấu hiệu: "Chèn vào mảng đã sắp xếp" → đây chính là 1 bước của Insertion Sort.
Thuật toán: Insertion Sort — thao tác chèn cốt lõi.

⚡ C++ — Card Night

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> hand;

    for (int i = 0; i < n; i++) {
        int card;
        cin >> card;

        // Tìm vị trí chèn (dùng lower_bound từ <algorithm>)
        auto pos = lower_bound(hand.begin(), hand.end(), card);
        hand.insert(pos, card);

        // In trạng thái tay bài
        for (int j = 0; j < hand.size(); j++) {
            cout << hand[j];
            if (j < hand.size() - 1) cout << " ";
        }
        cout << "\n";
    }

    return 0;
}

💡 Điểm nhấn

lower_bound() từ <algorithm> dùng Binary Search → tìm vị trí chèn trong O(log n). Nhưng vector::insert() vẫn O(n) vì phải dịch phần tử.

📚 Bài 2 — The Sliding Bookshelf & Moving Day

📋 Đề bài tóm tắt

Sliding Bookshelf: Đếm tổng số lần dịch chuyển (shifts) khi thực hiện Insertion Sort.
Moving Day: Đếm tổng số lần hoán đổi (swaps) khi thực hiện Selection Sort.

Shifts → Insertion Sort

Mỗi phép a[j+1] = a[j] là 1 shift. Đếm trong vòng while.

Swaps → Selection Sort

Mỗi phép swap(a[i], a[minIdx]) khi minIdx ≠ i là 1 swap.

⚡ C++ — Đếm Shifts (Insertion Sort)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    long long totalShifts = 0;

    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
            totalShifts++;  // Đếm mỗi phép dịch
        }
        a[j + 1] = key;
    }

    cout << totalShifts << endl;
    return 0;
}

⚡ C++ — Đếm Swaps (Selection Sort)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int totalSwaps = 0;

    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIdx]) minIdx = j;
        }
        if (minIdx != i) {
            swap(a[i], a[minIdx]);
            totalSwaps++;  // Đếm mỗi phép swap
        }
    }

    cout << totalSwaps << endl;
    return 0;
}

⚖️ Bài 3 — HR Records & The Broken Lottery

📋 Đề bài tóm tắt

Cho danh sách các bản ghi có cùng giá trị nhưng khác tên/ID. Sử dụng một thuật toán sắp xếp và kiểm tra xem thứ tự ban đầu của các phần tử bằng nhau có được giữ nguyên không.

🔍 Mục đích bài toán

Đây là minh chứng trực quan cho khái niệm Stability. Insertion Sort (stable) sẽ giữ nguyên thứ tự, Selection Sort (unstable) có thể phá vỡ.

📊 Ví dụ minh chứng

Input: [(3, "Lan"), (1, "Hoa"), (3, "Minh"), (2, "An")] — sắp theo giá trị số

Insertion Sort (Stable ✅)

(1,Hoa) (2,An) (3,Lan) (3,Minh)

Lan vẫn trước Minh ✅

Selection Sort (Unstable ❌)

(1,Hoa) (2,An) (3,Minh) (3,Lan)

Minh lại đứng trước Lan ❌

⚡ C++ — Stable sort với pair

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<pair<int, string>> records(n);
    for (int i = 0; i < n; i++) {
        cin >> records[i].first >> records[i].second;
    }

    // stable_sort từ <algorithm> — đảm bảo stable!
    stable_sort(records.begin(), records.end(),
        [](const auto& a, const auto& b) {
            return a.first < b.first;
        });

    for (auto& [val, name] : records) {
        cout << val << " " << name << "\n";
    }
    return 0;
}

✂️ Bài 4 — Team Divider (Partitioning)

📋 Đề bài tóm tắt

Cho một mảng và một giá trị pivot. Phân chia mảng thành 2 nhóm: các phần tử ≤ pivot ở bên trái, > pivot ở bên phải. In ra mảng sau phân hoạch.

🔍 Nhận diện

Đây chính là 1 bước của QuickSort — thao tác Partition (Lomuto).

⚡ C++ — Partition Step

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, pivot;
    cin >> n >> pivot;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // Partition: dùng partition từ <algorithm>
    // Hoặc tự code Lomuto:
    int i = 0;
    for (int j = 0; j < n; j++) {
        if (a[j] <= pivot) {
            swap(a[i], a[j]);
            i++;
        }
    }

    // In kết quả
    for (int x : a) cout << x << " ";
    cout << endl;

    // Hoặc dùng std::partition
    // auto it = partition(a.begin(), a.end(),
    //     [&](int x) { return x <= pivot; });

    return 0;
}

🔥 Bài 5 — How Chaotic Is This Playlist

📋 Đề bài tóm tắt

Đếm số nghịch thế (inversions) trong mảng. Một nghịch thế là cặp (i, j) mà i < j nhưng a[i] > a[j]. Đây là thước đo "mức độ hỗn loạn" của mảng.

⚠️ Bẫy thường gặp

Brute force O(n²) duyệt mọi cặp → TLE với n lớn. Tuyệt chiêu: biến đổi Merge Sort để đếm nghịch thế trong O(n log n)!

🧠 Ý tưởng cốt lõi: Đếm inversions trong bước Merge

Khi merge 2 nửa đã sắp xếp [L] và [R]: nếu R[j] < L[i], thì tất cả phần tử từ L[i..mid] đều tạo nghịch thế với R[j] → cộng thêm (mid - i + 1) inversions.

⚡ C++ — Đếm Inversions bằng Merge Sort

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

long long mergeCount(vector<int>& a, int lo, int mid, int hi) {
    vector<int> temp;
    long long count = 0;
    int i = lo, j = mid + 1;

    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) {
            temp.push_back(a[i++]);
        } else {
            temp.push_back(a[j++]);
            count += (mid - i + 1);  // ← Đếm inversions!
        }
    }
    while (i <= mid) temp.push_back(a[i++]);
    while (j <= hi) temp.push_back(a[j++]);

    for (int k = lo; k <= hi; k++)
        a[k] = temp[k - lo];

    return count;
}

long long mergeSortCount(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return 0;
    int mid = lo + (hi - lo) / 2;
    long long count = 0;
    count += mergeSortCount(a, lo, mid);
    count += mergeSortCount(a, mid + 1, hi);
    count += mergeCount(a, lo, mid, hi);
    return count;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    cout << mergeSortCount(a, 0, n - 1) << endl;
    return 0;
}

💡 Tại sao dùng Merge Sort?

Trong bước merge, khi phần tử phải (R[j]) nhỏ hơn phần tử trái (L[i]), ta biết chắc tất cả phần tử còn lại bên trái (L[i..mid]) đều lớn hơn R[j] → mỗi cái đều là 1 inversion. Cộng dồn → tổng inversions trong O(n log n).

🏆 Bài 6 — Honor Roll Integrity

📋 Đề bài tóm tắt

Sắp xếp danh sách sinh viên theo đa tiêu chí: giảm dần theo điểm, nếu điểm bằng thì tăng dần theo tên. Yêu cầu dùng thuật toán Counting Sort biến thể.

🔍 Bẻ khóa bài toán

Counting Sort thường dùng cho integer. Nhưng ta có thể: Counting Sort theo điểm (integer), trong mỗi bucket giữ thứ tự tên (hoặc sắp lại alphabet). Vì Counting Sort stable → thứ tự tên được bảo toàn!

⚡ C++ — Honor Roll (Counting Sort + stable)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<pair<int, string>> students(n);
    int maxScore = 0;

    for (int i = 0; i < n; i++) {
        cin >> students[i].second >> students[i].first;
        maxScore = max(maxScore, students[i].first);
    }

    // Bước 1: Sắp theo tên trước (tiêu chí phụ)
    stable_sort(students.begin(), students.end(),
        [](const auto& a, const auto& b) {
            return a.second < b.second;
        });

    // Bước 2: Counting Sort theo điểm (giảm dần)
    // Tạo buckets cho mỗi điểm
    vector<vector<pair<int, string>>> buckets(maxScore + 1);

    for (auto& s : students) {
        buckets[s.first].push_back(s);
    }

    // Duyệt từ điểm cao → thấp (giảm dần)
    for (int score = maxScore; score >= 0; score--) {
        for (auto& s : buckets[score]) {
            cout << s.second << " " << s.first << "\n";
        }
    }

    return 0;
}

💡 Bí quyết sắp xếp đa tiêu chí

Sắp xếp theo tiêu chí phụ trước, rồi tiêu chí chính sau bằng thuật toán stable. Vì stable giữ nguyên thứ tự tiêu chí phụ → kết quả đúng cả 2 tiêu chí!

Hoặc đơn giản hơn: dùng stable_sort với custom comparator xử lý cả 2 tiêu chí cùng lúc.

🎯 Tóm tắt Chương 5 — Bảng ánh xạ Bài toán → Thuật toán

Bài toán	Thuật toán cốt lõi	Kỹ thuật chính
Card Night	Insertion Sort	Chèn + lower_bound
Sliding Bookshelf	Insertion Sort	Đếm shifts
Moving Day	Selection Sort	Đếm swaps
HR Records	Stable Sort	Stability concept
Team Divider	QuickSort Partition	Lomuto partition
Chaotic Playlist	Merge Sort	Inversions count
Honor Roll	Counting Sort	Multi-key + stable

← Chương 4: Linked List 🏠 Trang chủ

Tuyển Tập Bóc TáchBài Toán Ứng Dụng Thực Tế

🃏 Bài 1 — Card Night

📚 Bài 2 — The Sliding Bookshelf & Moving Day

⚖️ Bài 3 — HR Records & The Broken Lottery

✂️ Bài 4 — Team Divider (Partitioning)

🔥 Bài 5 — How Chaotic Is This Playlist

🏆 Bài 6 — Honor Roll Integrity

Tuyển Tập Bóc Tách
Bài Toán Ứng Dụng Thực Tế