Bài 25.4: Tối ưu không gian nhớ trong Meet in the middle

Chào mừng trở lại với series blog về CTDL và Giải thuật!

Chúng ta đã cùng nhau tìm hiểu về kỹ thuật Meet-in-the-Middle (MITM) đầy mạnh mẽ và khéo léo. MITM cho phép chúng ta giải quyết các bài toán có kích thước dữ liệu $N$ lớn hơn đáng kể so với brute force thông thường bằng cách chia bài toán thành hai nửa, giải quyết độc lập từng nửa, rồi tìm cách kết hợp kết quả. Thay vì độ phức tạp $O(2^N)$, MITM thường đưa nó về $O(2^{N/2} \cdot \text{merge_time})$.

Tuy nhiên, sức mạnh đó thường đi kèm với một "gót chân Achilles" khá đau đầu: không gian nhớ.

Trong MITM tiêu chuẩn, chúng ta thường cần lưu trữ toàn bộ các kết quả trung gian từ hai nửa của bài toán. Nếu kích thước của mỗi nửa là $N/2$, số lượng kết quả trung gian ở mỗi bên có thể lên tới $O(2^{N/2})$. Điều này có nghĩa là chúng ta cần $O(2^{N/2})$ không gian nhớ để lưu trữ chúng.

Hãy thử tính toán một chút:

Nếu $N=40$, $N/2=20$. $2^{20} \approx 1$ triệu. Lưu trữ hai danh sách, mỗi danh sách 1 triệu phần tử (ví dụ là int), tổng cộng khoảng $2 \times 10^6 \times 4$ bytes = 8MB. Vẫn chấp nhận được.
Nếu $N=50$, $N/2=25$. $2^{25} \approx 33.5$ triệu. Hai danh sách 33.5 triệu phần tử, tổng cộng khoảng $2 \times 33.5 \times 10^6 \times 4$ bytes $\approx$ 268MB. Có thể sẽ căng thẳng với giới hạn bộ nhớ (thường là 256MB hoặc 512MB trong các kỳ thi lập trình).
Nếu $N=60$, $N/2=30$. $2^{30} \approx 1$ tỷ. Hai danh sách 1 tỷ phần tử cần tới khoảng 8GB bộ nhớ cho kiểu int! Không thể chấp nhận được trong môi trường thi đấu.

Và quan trọng hơn, nếu mỗi "kết quả trung gian" không chỉ là một số đơn giản mà là một cấu trúc dữ liệu phức tạp hơn, hoặc chúng ta cần lưu trữ nhiều thông tin đi kèm với mỗi kết quả, thì bộ nhớ sẽ bùng nổ nhanh chóng hơn nữa.

Vậy làm thế nào để chúng ta "gặp nhau ở giữa" mà không cần mang theo toàn bộ hành lý của cả hai bên cùng lúc?

Kỹ thuật tối ưu không gian nhớ: Sắp xếp và Gặp gỡ hiệu quả

Mặc dù không thể hoàn toàn loại bỏ việc lưu trữ các kết quả trung gian $O(2^{N/2})$, chúng ta có thể tối ưu đáng kể không gian nhớ trong bước kết hợp (merge). Kỹ thuật kinh điển để làm điều này là kết hợp việc sắp xếp một hoặc cả hai danh sách kết quả trung gian, sau đó sử dụng các phương pháp tìm kiếm hoặc "gặp gỡ" hiệu quả trên các danh sách đã sắp xếp này, thay vì phải lưu trữ tất cả các cặp kết hợp tiềm năng (có thể lên tới $O(2^N)$).

Cụ thể, đối với nhiều bài toán MITM, bước kết hợp thường quy về việc tìm các cặp $(A_i, B_j)$ từ danh sách kết quả nửa đầu ($A$) và nửa sau ($B$) sao cho chúng thỏa mãn một điều kiện nào đó, ví dụ: $A_i + B_j = Target$, $A_i - B_j = Target$, $A_i \oplus B_j = Target$ (XOR), v.v.

Thay vì tạo ra một danh sách mới chứa tất cả các cặp $(A_i, B_j)$ và kiểm tra điều kiện (sẽ tốn $O(2^N)$ bộ nhớ), chúng ta có thể:

Sinh các kết quả trung gian cho nửa đầu và lưu vào danh sách list1.
Sinh các kết quả trung gian cho nửa sau và lưu vào danh sách list2.
Sắp xếp một trong hai danh sách (ví dụ, list2).
Duyệt qua từng phần tử trong danh sách còn lại (list1). Với mỗi phần tử x từ list1, chúng ta cần tìm (các) phần tử y trong list2 thỏa mãn điều kiện. Do list2 đã được sắp xếp, chúng ta có thể sử dụng tìm kiếm nhị phân (binary search) hoặc kỹ thuật hai con trỏ (two pointers) để tìm y một cách hiệu quả.

Kỹ thuật sắp xếp và hai con trỏ đặc biệt mạnh mẽ và tiết kiệm bộ nhớ khi điều kiện kết hợp có dạng tổng hoặc hiệu cố định.

Chúng ta vẫn cần $O(2^{N/2})$ bộ nhớ để lưu trữ list1 và list2. Tuy nhiên, bước kết hợp chỉ cần thêm một lượng bộ nhớ không đáng kể ($O(1)$ hoặc $O(\log(2^{N/2})) = O(N)$ cho stack đệ quy của binary search), thay vì $O(2^N)$ như cách làm "ghép cặp tất cả".

Hãy đi sâu vào một ví dụ cụ thể để thấy rõ điều này.

Ví dụ minh hoạ: Đếm cặp tổng bằng Target

Bài toán: Cho một tập hợp $N$ số nguyên dương. Đếm số lượng cặp tập con (một tập con chỉ chứa các số từ nửa đầu của tập hợp ban đầu, tập con còn lại chứa các số từ nửa sau) sao cho tổng của các số trong hai tập con đó cộng lại bằng đúng $Target$. (Lưu ý: Một số có thể được sử dụng trong tập con của nửa tương ứng của nó hoặc không, giống bài toán Subset Sum cơ bản).

Ví dụ $N=40$. Chia thành 20 số đầu và 20 số cuối. Ta cần tìm số cặp (tập con $S_1$ từ 20 số đầu, tập con $S_2$ từ 20 số cuối) sao cho $\sum_{x \in S_1} x + \sum_{y \in S_2} y = Target$.

Cách tiếp cận MITM tiêu chuẩn:

Sinh tất cả các tổng tập con có thể có từ 20 số đầu. Lưu vào vector sums1. Kích thước sums1 có thể lên tới $2^{20}$.
Sinh tất cả các tổng tập con có thể có từ 20 số cuối. Lưu vào vector sums2. Kích thước sums2 có thể lên tới $2^{20}$.
Sắp xếp sums2.
Với mỗi s1 trong sums1, tìm số lượng s2 trong sums2 sao cho s1 + s2 = Target, tức s2 = Target - s1. Dùng tìm kiếm nhị phân trên sums2 để đếm số lượng phần tử bằng Target - s1. Cộng dồn kết quả.

Cách này cần $O(2^{N/2})$ bộ nhớ để lưu sums1 và sums2. Bước 3 mất $O(2^{N/2} \log 2^{N/2})$ thời gian. Bước 4 mất $O(2^{N/2} \log 2^{N/2})$ thời gian. Tổng thời gian $O(2^{N/2} \log 2^{N/2})$, bộ nhớ $O(2^{N/2})$. Với $N=40$, điều này chấp nhận được. Với $N=50$, bộ nhớ bắt đầu là vấn đề.

Tối ưu không gian nhớ (bằng cách sử dụng Kỹ thuật Hai Con Trỏ trong bước merge):

Chúng ta vẫn cần sinh và lưu trữ sums1 và sums2, nên bộ nhớ cơ bản vẫn là $O(2^{N/2})$. Kỹ thuật hai con trỏ giúp chúng ta kết hợp hai danh sách này để đếm cặp một cách hiệu quả về thời gian và quan trọng là không tạo ra cấu trúc dữ liệu tạm thời khổng lồ trong bước merge, giữ mức bộ nhớ ở $O(2^{N/2})$.

Sinh các tổng tập con cho nửa đầu vào sums1.
Sinh các tổng tập con cho nửa sau vào sums2.
Sắp xếp cả sums1 và sums2.
Sử dụng kỹ thuật hai con trỏ để đếm các cặp (s1, s2) với s1 từ sums1, s2 từ sums2 sao cho s1 + s2 = Target.

Cách sử dụng hai con trỏ trên hai danh sách đã sắp xếp để tìm cặp tổng bằng Target hoạt động như sau:

Đặt một con trỏ i ở đầu sums1 (index 0).
Đặt một con trỏ j ở cuối sums2 (index sums2.size() - 1).
Tổng số cặp đếm được khởi tạo là count = 0.
Lặp chừng nào i < sums1.size() và j >= 0:
- Tính tổng hiện tại current_sum = sums1[i] + sums2[j].
- Nếu current_sum == Target: Ta tìm được một cặp thỏa mãn. Tuy nhiên, có thể có nhiều phần tử sums1[i] giống nhau và nhiều phần tử sums2[j] giống nhau. Ta cần đếm tất cả các cặp có thể tạo ra tổng này. Đếm số lượng phần tử liên tiếp bằng sums1[i] bắt đầu từ i (gọi là count1). Đếm số lượng phần tử liên tiếp bằng sums2[j] kết thúc tại j (gọi là count2). Số cặp mới tìm được là count1 * count2. Cộng số này vào count. Sau đó, dịch chuyển con trỏ i tiến lên qua các phần tử sums1[i] vừa xét (i += count1) và dịch chuyển con trỏ j lùi lại qua các phần tử sums2[j] vừa xét (j -= count2).
- Nếu current_sum < Target: Tổng hiện tại nhỏ quá. Cần tăng tổng lên. Vì sums2 đã sắp xếp tăng dần và ta đang ở cuối (j), giảm j sẽ giảm tổng. Do đó, ta phải tăng sums1[i] bằng cách i++.
- Nếu current_sum > Target: Tổng hiện tại lớn quá. Cần giảm tổng xuống. Tăng i sẽ tăng tổng. Do đó, ta phải giảm sums2[j] bằng cách j--.

Kỹ thuật hai con trỏ này giúp ta tìm tất cả các cặp trong $O(|sums1| + |sums2|)$ thời gian sau khi đã sắp xếp, tức $O(2^{N/2})$ thời gian. Tổng thời gian cho bước merge là $O(2^{N/2} \log 2^{N/2})$ (do sắp xếp) + $O(2^{N/2})$ (do hai con trỏ) = $O(2^{N/2} \log 2^{N/2})$. Bộ nhớ vẫn là $O(2^{N/2})$ cho sums1 và sums2.

Đây là cách tối ưu bộ nhớ trong MITM: Chúng ta chấp nhận lưu trữ $O(2^{N/2})$ kết quả trung gian, nhưng sử dụng các kỹ thuật hiệu quả (như sắp xếp + hai con trỏ hoặc hash map) để kết hợp chúng mà không cần $O(2^N)$ bộ nhớ cho bước merge.

Hãy xem mã C++ cho ví dụ Subset Sum Counting với kỹ thuật này.

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <map> // Có thể dùng cho các biến thể khác hoặc để đếm tần suất nhanh hơn

// Hàm đệ quy sinh ra tất cả các tổng tập con
// nums: mảng các số ban đầu
// index: vị trí hiện tại đang xét trong nums
// current_sum: tổng của tập con đang xây dựng
// sums: vector để lưu trữ các tổng tập con
// end_index: vị trí kết thúc của nửa mảng đang xét
void generate_subset_sums(const std::vector<int>& nums, int index, long long current_sum, std::vector<long long>& sums, int end_index) {
    // Điều kiện dừng: đã xét hết các phần tử trong nửa mảng
    if (index == end_index) {
        sums.push_back(current_sum);
        return;
    }

    // Trường hợp 1: Không chọn phần tử nums[index]
    generate_subset_sums(nums, index + 1, current_sum, sums, end_index);

    // Trường hợp 2: Chọn phần tử nums[index]
    generate_subset_sums(nums, index + 1, current_sum + nums[index], sums, end_index);
}

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

    int N;
    long long Target;
    std::cin >> N >> Target;

    std::vector<int> nums(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> nums[i];
    }

    // Chia mảng thành hai nửa
    int mid = N / 2;
    std::vector<int> first_half(nums.begin(), nums.begin() + mid);
    std::vector<int> second_half(nums.begin() + mid, nums.end());

    // Sinh tổng tập con cho hai nửa
    std::vector<long long> sums1, sums2;
    generate_subset_sums(nums, 0, 0, sums1, mid); // Sinh từ nums[0] đến nums[mid-1]
    generate_subset_sums(nums, mid, 0, sums2, N); // Sinh từ nums[mid] đến nums[N-1]

    // Tối ưu bộ nhớ và thời gian merge: Sắp xếp và dùng Hai con trỏ
    std::sort(sums1.begin(), sums1.end());
    std::sort(sums2.begin(), sums2.end());

    long long count = 0;
    int i = 0; // Con trỏ cho sums1 (bắt đầu từ đầu)
    int j = sums2.size() - 1; // Con trỏ cho sums2 (bắt đầu từ cuối)

    while (i < sums1.size() && j >= 0) {
        long long current_sum = sums1[i] + sums2[j];

        if (current_sum == Target) {
            // Tìm thấy cặp tổng bằng Target.
            // Cần đếm số lượng các phần tử trùng lặp để tính đúng số cặp.

            // Đếm số lần xuất hiện của sums1[i] liên tiếp
            long long current_s1 = sums1[i];
            long long count1 = 0;
            while (i < sums1.size() && sums1[i] == current_s1) {
                count1++;
                i++;
            }

            // Đếm số lần xuất hiện của sums2[j] liên tiếp
            long long current_s2 = sums2[j];
            long long count2 = 0;
            while (j >= 0 && sums2[j] == current_s2) {
                count2++;
                j--;
            }

            // Mỗi phần tử trong count1 * count2 cặp này đều có tổng bằng Target
            count += count1 * count2;

        } else if (current_sum < Target) {
            // Tổng hiện tại nhỏ hơn Target, cần tăng tổng.
            //sums1 đã tăng dần, sums2 đã tăng dần.
            // i++ sẽ tăng sums1[i], làm tăng current_sum.
            // j-- sẽ giảm sums2[j], làm giảm current_sum.
            // Vì cần tăng tổng, ta dịch i lên.
            i++;
        } else { // current_sum > Target
            // Tổng hiện tại lớn hơn Target, cần giảm tổng.
            // Dịch j xuống để giảm sums2[j], làm giảm current_sum.
            j--;
        }
    }

    std::cout << count << std::endl;

    return 0;
}

Giải thích mã C++:

generate_subset_sums function: Đây là một hàm đệ quy (có thể hiểu như một dạng backtracking đơn giản) để sinh ra tất cả các tổng tập con có thể có từ một nửa của mảng số ban đầu.
- nums: Mảng chứa các số đầu vào.
- index: Chỉ số của phần tử đang xét trong mảng nums.
- current_sum: Tổng của các phần tử đã được chọn cho đến thời điểm hiện tại.
- sums: Vector long long để lưu trữ tất cả các current_sum cuối cùng khi đệ quy dừng.
- end_index: Chỉ số đánh dấu kết thúc của nửa mảng hiện tại (không bao gồm end_index).
- Điều kiện dừng: Khi index đạt đến end_index, tức là chúng ta đã xét qua tất cả các phần tử trong nửa mảng này, tổng current_sum hiện tại là một tổng tập con hợp lệ, và nó được thêm vào vector sums.
- Bước đệ quy: Tại mỗi index, chúng ta có hai lựa chọn: không bao gồm nums[index] vào tập con (gọi đệ quy với index + 1 và current_sum giữ nguyên) hoặc bao gồm nums[index] (gọi đệ quy với index + 1 và current_sum cộng thêm nums[index]).
main function:
- Đọc $N$ và $Target$.
- Đọc $N$ số vào vector nums.
- Chia $N$ thành mid = N / 2.
- Tạo hai vector sums1 và sums2.
- Gọi generate_subset_sums để sinh tổng cho nửa đầu (từ index 0 đến mid-1, lưu vào sums1) và nửa sau (từ index mid đến N-1, lưu vào sums2).
- Đây là bước chuẩn bị cho tối ưu merge: Sắp xếp cả sums1 và sums2. Việc này tốn thời gian $O(2^{N/2} \log 2^{N/2})$ nhưng rất quan trọng cho bước tiếp theo.
- Khởi tạo count = 0 để đếm số cặp.
- Khởi tạo hai con trỏ i cho sums1 (bắt đầu từ đầu) và j cho sums2 (bắt đầu từ cuối).
- Vòng lặp while (i < sums1.size() && j >= 0) là trái tim của kỹ thuật hai con trỏ. Nó duyệt qua tất cả các cặp tiềm năng một cách hiệu quả mà không cần tạo ra chúng.
- Bên trong vòng lặp:
  - Tính current_sum = sums1[i] + sums2[j].
  - Nếu current_sum == Target: Ta tìm được một cặp. Tuy nhiên, để đếm tất cả các cặp thỏa mãn khi có số trùng lặp, ta cần đếm số lượng phần tử bằng sums1[i] liên tiếp (bằng một vòng while khác và lưu vào count1) và số lượng phần tử bằng sums2[j] liên tiếp (từ cuối về, lưu vào count2). Số cặp mới đóng góp vào tổng là count1 * count2. Sau khi đếm, ta dịch chuyển i và j qua các phần tử trùng lặp vừa xử lý.
  - Nếu current_sum < Target: Tổng quá nhỏ, cần tăng nó lên. Vì sums1 đã sắp xếp tăng dần và i đang đi từ đầu, sums1[i] sẽ tăng khi i tăng. Vì sums2 đã sắp xếp tăng dần nhưng j đang đi từ cuối, sums2[j] sẽ giảm khi j giảm. Để tăng tổng sums1[i] + sums2[j], ta phải tăng sums1[i] bằng cách i++.
  - Nếu current_sum > Target: Tổng quá lớn, cần giảm nó xuống. Để giảm tổng sums1[i] + sums2[j], ta phải giảm sums2[j] bằng cách j--.
- Cuối cùng, in ra count.

Kỹ thuật hai con trỏ trên hai mảng đã sắp xếp này chỉ sử dụng $O(1)$ không gian bổ sung (cho các biến i, j, count, current_sum, v.v.) trong vòng lặp chính. Toàn bộ không gian nhớ chủ yếu dùng để lưu trữ hai vector sums1 và sums2, là $O(2^{N/2})$. Đây chính là cách chúng ta tối ưu bộ nhớ cho bước merge trong MITM, giữ cho bài toán có thể giải được với các giá trị $N$ lớn hơn.

Khi nào kỹ thuật này hiệu quả?

Kỹ thuật sắp xếp + hai con trỏ để tối ưu bước merge đặc biệt hiệu quả khi:

Bài toán MITM của bạn yêu cầu tìm/đếm các cặp từ hai danh sách trung gian có tổng hoặc hiệu bằng một giá trị cố định (A[i] + B[j] = Target hoặc A[i] - B[j] = Target).
Việc sắp xếp các danh sách trung gian là khả thi về mặt thời gian ($O(2^{N/2} \log 2^{N/2})$ chấp nhận được).
Bạn muốn tránh bộ nhớ $O(2^N)$ nếu cố gắng tạo ra tất cả các cặp kết hợp tiềm năng.

Đối với các điều kiện kết hợp khác, ví dụ A[i] XOR B[j] = Target, kỹ thuật hai con trỏ trên mảng sắp xếp không còn trực tiếp áp dụng. Tuy nhiên, bạn vẫn có thể tối ưu bước merge bằng cách sắp xếp một danh sách và dùng tìm kiếm nhị phân trên danh sách kia (như mô tả ở trên, tốn $O(2^{N/2})$ bộ nhớ), hoặc lưu trữ một danh sách vào std::unordered_set hoặc std::unordered_map (tốn $O(2^{N/2})$ bộ nhớ trung bình) và duyệt danh sách còn lại để tìm kiếm. Kỹ thuật sắp xếp + hai con trỏ là một trường hợp cụ thể và rất hiệu quả cho các bài toán tổng/hiệu.

Bài tập ví dụ:

Sắp xếp Hamming

Trong giờ học thuật toán, FullHouse Dev được thầy giáo giao cho một bài toán thú vị về khoảng cách Hamming.

Bài toán

Cho một mảng số nguyên $A$ và một số nguyên $X$, nhiệm vụ của bạn là cài đặt một thuật toán sắp xếp. Mục tiêu là sắp xếp các phần tử trong mảng $A$ dựa trên Khoảng cách Hamming của chúng với số nguyên $X$.

Khoảng cách Hamming được định nghĩa là số bit khác nhau trong biểu diễn nhị phân của hai số nguyên.

Việc sắp xếp phải được thực hiện theo thứ tự tăng dần của khoảng cách Hamming, và trong trường hợp các phần tử có cùng khoảng cách Hamming, chúng sẽ được sắp xếp theo thứ tự số học tăng dần.

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên $T$ - số lượng test case.
Với mỗi test case:
- Dòng đầu tiên chứa hai số nguyên $N$ và $X$.
- Dòng thứ hai chứa mảng $A$ gồm $N$ phần tử.

OUTPUT FORMAT:

Với mỗi test case, in ra mảng đã được sắp xếp theo quy tắc trên trên một dòng mới.

Ràng buộc:

$1 \leq T \leq 100$
$1 \leq N \leq 10^5$
$1 \leq A[i], X \leq 10^9$

Ví dụ

INPUT

1
3 2
4 5 6

OUTPUT

6 4 5

Giải thích

Trong ví dụ này, biểu diễn nhị phân của $X = 2$ là "10". Tương tự, với mảng $A$, biểu diễn nhị phân của các phần tử là:

4: "100"
5: "101"
6: "110"

Khoảng cách Hamming của mỗi phần tử trong mảng với $X$ là:

H(4,2) = 1
H(5,2) = 2
H(6,2) = 1

Do 4 và 6 có cùng khoảng cách Hamming là 1, chúng được sắp xếp theo thứ tự số học. Vì vậy, kết quả cuối cùng là: 6 4 5. Chào bạn, đây là hướng dẫn giải ngắn gọn cho bài toán "Sắp xếp Hamming" bằng C++:

Hiểu rõ tiêu chí sắp xếp: Cần sắp xếp mảng A dựa trên hai tiêu chí theo thứ tự ưu tiên:
- Thứ nhất: Khoảng cách Hamming với số X (tăng dần).
- Thứ hai: Giá trị của chính phần tử đó (tăng dần) - dùng khi hai phần tử có cùng khoảng cách Hamming với X.
Tính Khoảng cách Hamming: Khoảng cách Hamming giữa hai số nguyên a và b là số lượng bit khác nhau trong biểu diễn nhị phân của chúng. Điều này tương đương với việc tính số lượng bit 1 trong kết quả của phép toán XOR (^) giữa a và b (tức là a ^ b).
- Để đếm số bit 1 (population count) trong một số, bạn có thể sử dụng vòng lặp dịch bit hoặc các hàm tích hợp sẵn của trình biên dịch (ví dụ: __builtin_popcount trong GCC/Clang) để tối ưu tốc độ.
Sử dụng hàm sắp xếp với comparator tùy chỉnh: C++ cung cấp hàm std::sort trong thư viện <algorithm>. Hàm này cho phép bạn truyền vào một hàm so sánh (comparator) tùy chỉnh để định nghĩa quy tắc sắp xếp.
- Hàm so sánh này sẽ nhận hai phần tử từ mảng (gọi là a và b) và phải trả về true nếu a được xếp trước b, và false nếu ngược lại.
Xây dựng logic cho hàm so sánh (comparator):
- Đối với hai phần tử a và b:
  - Tính khoảng cách Hamming của a với X (gọi là dist_a).
  - Tính khoảng cách Hamming của b với X (gọi là dist_b).
  - So sánh dist_a và dist_b:
    - Nếu dist_a < dist_b, thì a nên đứng trước b. Trả về true.
    - Nếu dist_a > dist_b, thì a không nên đứng trước b. Trả về false.
    - Nếu dist_a == dist_b (hai khoảng cách bằng nhau): Tiếp tục so sánh theo giá trị của phần tử.
      - Nếu a < b, thì a nên đứng trước b. Trả về true.
      - Nếu a >= b, thì a không nên đứng trước b. Trả về false.
Cấu trúc chương trình:
- Đọc số lượng test case T.
- Lặp T lần:
  - Đọc N và X.
  - Đọc mảng A gồm N phần tử.
  - Gọi std::sort trên mảng A, truyền vào hàm so sánh tùy chỉnh đã định nghĩa ở bước 4 (lưu ý hàm so sánh này cần truy cập được giá trị của X, có thể dùng lambda expression và capture X).
  - In ra các phần tử của mảng A sau khi đã sắp xếp.

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

Comments

There are no comments at the moment.