Bài 25.5. Kỹ thuật Meet-in-the-Middle (MITM) - Bài tập tổng hợp

Chào mừng trở lại với series Cấu trúc dữ liệu và Giải thuật!

Trong thế giới của lập trình thi đấu hay đơn giản là giải quyết các bài toán tối ưu, chúng ta thường xuyên đối mặt với những vấn đề có độ phức tạp theo cấp số mũ, chẳng hạn như duyệt qua tất cả các tập con của một tập hợp (O(2^N)) hoặc tất cả các hoán vị (O(N!)). Với N nhỏ (khoảng dưới 20), O(2^N) có thể chấp nhận được, nhưng khi N lớn hơn (khoảng 30-40), nó trở nên bất khả thi.

Vậy làm sao để "đánh bại" độ phức tạp theo cấp số mũ này? Một trong những kỹ thuật mạnh mẽ giúp chúng ta làm điều đó chính là Meet-in-the-Middle (MITM), hay còn gọi là "Gặp gỡ ở giữa".

MITM không phải là một giải thuật hoàn toàn mới mẻ, mà là một kỹ thuật tối ưu dựa trên ý tưởng chia để trị, nhưng với một cách tiếp cận đặc biệt ở bước "kết hợp". Thay vì giải quyết hoàn toàn hai nửa bài toán một cách độc lập rồi mới kết hợp, MITM giải quyết một phần của bài toán ở mỗi nửa, lưu trữ các kết quả trung gian, và sau đó tìm cách kết hợp hiệu quả các kết quả này để tìm ra lời giải cuối cùng.

Ý tưởng cốt lõi là: nếu một bài toán có thể chia thành hai phần gần như độc lập và lời giải cuối cùng là sự kết hợp của một kết quả từ phần đầu và một kết quả từ phần sau, chúng ta có thể giảm độ phức tạp từ O(2^N) xuống khoảng O(2^(N/2)). Điều này là bởi vì chúng ta chỉ phải duyệt qua 2^(N/2) khả năng cho mỗi nửa thay vì 2^N khả năng cho toàn bộ.

Ý tưởng chính của Kỹ thuật Meet-in-the-Middle:

Chia bài toán: Tách dữ liệu đầu vào (ví dụ: một mảng arr kích thước N) thành hai nửa: nửa đầu (từ 0 đến N/2 - 1) và nửa sau (từ N/2 đến N - 1).
Giải quyết độc lập (một phần): Đối với mỗi nửa, tạo ra tất cả các kết quả có thể có cho phần đó của bài toán. Ví dụ, nếu bài toán là tìm tổng con, bạn sẽ tạo ra tất cả các tổng con có thể từ nửa đầu và tất cả các tổng con có thể từ nửa sau. Lưu trữ các kết quả này vào hai tập hợp/danh sách riêng biệt.
Gặp gỡ ở giữa: Đây là bước quan trọng nhất. Thay vì duyệt qua tất cả các cặp kết quả (một từ tập hợp thứ nhất, một từ tập hợp thứ hai) một cách ngây thơ (có thể vẫn là O(2^(N/2) 2^(N/2)) = O(2^N)), chúng ta cần một cách hiệu quả để tìm kiếm sự kết hợp phù hợp. Thường thì, chúng ta sẽ sắp xếp một trong hai tập hợp kết quả và sau đó sử dụng tìm kiếm nhị phân hoặc kỹ thuật two pointers* trên tập hợp đã sắp xếp để tìm các kết quả kết hợp với các phần tử từ tập hợp còn lại một cách nhanh chóng.

Độ phức tạp lúc này sẽ bao gồm:

Tạo kết quả cho nửa đầu: O(2^(N/2))
Tạo kết quả cho nửa sau: O(2^((N-N/2))) ≈ O(2^(N/2))
Sắp xếp một tập hợp kết quả: O(2^(N/2) log(2^(N/2))) ≈ O(2^(N/2) N/2)
Kết hợp (ví dụ: duyệt tập hợp thứ nhất và tìm kiếm nhị phân trên tập hợp thứ hai): O(2^(N/2) log(2^(N/2))) ≈ O(2^(N/2) N/2)

Tổng cộng, độ phức tạp thời gian giảm đáng kể xuống còn khoảng O(2^(N/2) * N/2). Tuy nhiên, chúng ta phải trả giá bằng độ phức tạp không gian để lưu trữ các kết quả trung gian, thường là O(2^(N/2)). Đây là sự đánh đổi thường thấy: giảm thời gian, tăng không gian.

Hãy cùng đi sâu vào các ví dụ cụ thể để thấy rõ sức mạnh của MITM.

Ví dụ 1: Kiểm tra xem có tập con nào có tổng bằng K không?

Bài toán: Cho một mảng gồm N số nguyên arr và một số nguyên K. Xác định xem có tồn tại một tập con (subset) của arr mà tổng các phần tử trong tập con đó bằng K hay không.

Constraints: N có thể lên tới 40. Các phần tử trong arr có thể dương, âm hoặc bằng 0.
Phân tích:
- Cách tiếp cận vét cạn (brute force): Duyệt qua tất cả 2^N tập con của arr, tính tổng của từng tập con và kiểm tra xem có bằng K không. Độ phức tạp O(2^N * N) (hoặc O(2^N) nếu tính tổng nhanh hơn). Với N=40, 2^40 là quá lớn (khoảng 10^12), không thể chạy kịp.
- Cách tiếp cận Quy hoạch động (ví dụ: dp[i][s] là có thể tạo tổng s từ i phần tử đầu tiên). Độ phức tạp O(N * Tổng_Max), cũng không khả thi nếu Tổng_Max lớn.
Áp dụng Meet-in-the-Middle:
1. Chia mảng arr thành hai nửa: arr1 (từ index 0 đến N/2 - 1) và arr2 (từ index N/2 đến N - 1). Kích thước mỗi nửa khoảng N/2.
2. Tạo danh sách sums1: Chứa tất cả các tổng con có thể có được từ các phần tử trong arr1. Có 2^(N/2) tổng như vậy.
3. Tạo danh sách sums2: Chứa tất cả các tổng con có thể có được từ các phần tử trong arr2. Có 2^((N - N/2)) tổng như vậy.
4. Vấn đề bây giờ trở thành: Chúng ta cần tìm xem có tồn tại s1 trong sums1 và s2 trong sums2 sao cho s1 + s2 = K hay không. Điều này tương đương với việc tìm xem có tồn tại s1 trong sums1 và K - s1 trong sums2 hay không.
5. Để tìm kiếm hiệu quả K - s1 trong sums2, chúng ta sắp xếp danh sách sums2.
6. Duyệt qua từng tổng s1 trong sums1. Với mỗi s1, sử dụng tìm kiếm nhị phân (binary search) trên danh sách sums2 để xem K - s1 có tồn tại trong đó không. Nếu tìm thấy dù chỉ một lần, ta kết luận là có tồn tại tập con tổng bằng K và dừng lại.
7. Nếu duyệt hết sums1 mà không tìm thấy cặp nào, thì không tồn tại tập con tổng bằng K.
Độ phức tạp với MITM:
- Tạo sums1: O(2^(N/2)) tổng. Mỗi tổng cần duyệt N/2 phần tử trong trường hợp đệ quy vét cạn thông thường, hoặc O(N/2 2^(N/2)) nếu tính tổng cẩn thận. Tuy nhiên, việc sinh tất cả các tổng có thể thực hiện trong O(2^(N/2)) bằng đệ quy hiệu quả hơn. Tổng cộng: O(N/2 2^(N/2)) nếu tính cả thời gian sinh, hoặc O(2^(N/2)) nếu chỉ tính số lượng kết quả sinh ra và thời gian sinh mỗi kết quả trung bình là O(1). Thời gian sinh tất cả 2^(N/2) tổng thường là O(N/2 2^(N/2)). Let's assume the recursive generation takes O(2^(N/2)) state transitions, each doing O(1) work (adding/not adding), plus O(N/2) to build the sum in naive recursive way. A better way to generate sums iteratively or recursively is O(2^(N/2)). Let's stick to O(2^(N/2)) for generation time and O(N/2 2^(N/2)) if sums were explicitly built. The typical recursive generation is O(N/2 * 2^(N/2)).
- Tạo sums2: Tương tự, O((N-N/2) 2^((N-N/2))) ≈ O(N/2 2^(N/2)).
- Sắp xếp sums2: O(2^((N-N/2)) log(2^((N-N/2)))) ≈ O(2^(N/2) N/2).
- Duyệt sums1 và tìm kiếm nhị phân trên sums2: O(2^(N/2) log(2^((N-N/2)))) ≈ O(2^(N/2) N/2).
Tổng thời gian: O(N/2 2^(N/2)) + O(N/2 2^(N/2)) + O(2^(N/2) N/2) + O(2^(N/2) N/2) = O(N * 2^(N/2)). Hoặc nếu việc sinh tổng được tối ưu (thường là vậy), nó là O(N/2 * 2^(N/2)) hoặc thậm chí O(2^(N/2) * log(2^(N/2))) tùy thuộc vào cách tính thời gian sinh tổng và tìm kiếm. Tuy nhiên, O(N/2 2^(N/2)) là một ước tính tốt cho N=40, nó khoảng O(20 2^20), nhỏ hơn rất nhiều so với O(40 * 2^40).

Độ phức tạp không gian: O(2^(N/2)) để lưu trữ sums1 và sums2. Với N=40, 2^20 khoảng 10^6, lưu trữ 2 triệu số long long (mỗi số 8 byte) cần khoảng 16 MB, hoàn toàn khả thi.
C++ Code Implementation (Kiểm tra sự tồn tại):

#include <iostream>
#include <vector>
#include <numeric> // For std::accumulate (not used in recursive gen, but useful for sums)
#include <algorithm> // For std::sort and std::binary_search
#include <cmath> // For std::pow

using namespace std;

// Function to generate all possible subset sums recursively
// start: starting index for this half
// end: ending index for this half
// arr: the original array
// current_sum: the sum of elements included so far
// sums: vector to store generated sums
void generate_subset_sums(int start, int end, const vector<int>& arr, long long current_sum, vector<long long>& sums) {
    // Base case: if we have considered all elements in this half
    if (start > end) {
        sums.push_back(current_sum);
        return;
    }

    // Recursive step 1: exclude the current element
    generate_subset_sums(start + 1, end, arr, current_sum, sums);

    // Recursive step 2: include the current element
    generate_subset_sums(start + 1, end, arr, current_sum + arr[start], sums);
}

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

    int n;
    long long k;
    cin >> n >> k;

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

    // Split the array into two halves
    int mid = n / 2;

    vector<long long> sums1;
    vector<long long> sums2;

    // Generate subset sums for the first half
    generate_subset_sums(0, mid - 1, arr, 0, sums1);

    // Generate subset sums for the second half
    generate_subset_sums(mid, n - 1, arr, 0, sums2);

    // Sort sums2 for efficient searching
    sort(sums2.begin(), sums2.end());

    // Check if a pair of sums (s1 from sums1, s2 from sums2) exists such that s1 + s2 = k
    bool found = false;
    for (long long s1 : sums1) {
        // We need s2 = k - s1. Search for k - s1 in sums2.
        long long target_s2 = k - s1;
        if (binary_search(sums2.begin(), sums2.end(), target_s2)) {
            found = true;
            break; // Found a pair, no need to search further
        }
    }

    if (found) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

Giải thích Code:
- Hàm generate_subset_sums: Đây là hàm đệ quy để sinh tất cả các tổng con có thể từ một phạm vi index nhất định (start đến end) của mảng arr. Tại mỗi bước, chúng ta có hai lựa chọn cho phần tử arr[start]: hoặc không bao gồm nó (gọi đệ quy với start + 1 và current_sum giữ nguyên), hoặc bao gồm nó (gọi đệ quy với start + 1 và current_sum cộng thêm arr[start]). Điểm dừng là khi start > end, tức là đã duyệt qua tất cả các phần tử trong phạm vi, lúc này current_sum chính là một tổng con hợp lệ và được thêm vào vector sums.
- Trong main:
  - Đọc đầu vào n và k.
  - Đọc mảng arr.
  - Xác định điểm giữa mid = n / 2.
  - Gọi generate_subset_sums cho nửa đầu (0 đến mid - 1) lưu kết quả vào sums1.
  - Gọi generate_subset_sums cho nửa sau (mid đến n - 1) lưu kết quả vào sums2.
  - sort(sums2.begin(), sums2.end()): Sắp xếp sums2 là bước bắt buộc để có thể sử dụng tìm kiếm nhị phân.
  - Duyệt qua từng tổng s1 trong sums1.
  - Với mỗi s1, tính giá trị target_s2 = k - s1 cần tìm trong sums2.
  - binary_search(sums2.begin(), sums2.end(), target_s2): Hàm này kiểm tra xem target_s2 có tồn tại trong sums2 đã được sắp xếp hay không. Nó chạy trong thời gian O(log(|sums2|)).
  - Nếu binary_search trả về true, ta tìm thấy một cặp tổng thỏa mãn s1 + s2 = k, đặt found = true và thoát vòng lặp.
  - In kết quả dựa trên giá trị của found.
- Sử dụng long long cho các biến tổng (k, current_sum, sums1, sums2) để tránh tràn số, vì tổng của các số nguyên có thể vượt quá giới hạn của int.

Ví dụ 2: Đếm số lượng tập con có tổng bằng K

Bài toán: Cho một mảng gồm N số nguyên arr và một số nguyên K. Đếm xem có bao nhiêu tập con của arr mà tổng các phần tử trong tập con đó bằng K.

Constraints: Tương tự, N lên tới 40.
Phân tích: Cách tiếp cận vét cạn O(2^N * N) vẫn quá chậm. Quy hoạch động cũng gặp vấn đề với kích thước tổng. MITM là lựa chọn tốt.
Áp dụng Meet-in-the-Middle:
1. Chia mảng arr thành hai nửa arr1 và arr2 như ví dụ 1.
2. Tạo danh sách sums1 chứa tất cả tổng con từ arr1.
3. Tạo danh sách sums2 chứa tất cả tổng con từ arr2.
4. Vấn đề là đếm số cặp (s1, s2) sao cho s1 thuộc sums1, s2 thuộc sums2, và s1 + s2 = K. Tức là đếm số cặp (s1, s2) sao cho s1 thuộc sums1 và s2 = K - s1 thuộc sums2.
5. Sắp xếp danh sách sums2.
6. Duyệt qua từng tổng s1 trong sums1. Với mỗi s1, chúng ta cần đếm có bao nhiêu lần giá trị K - s1 xuất hiện trong sums2.
7. Để đếm số lần xuất hiện của một giá trị trong một mảng đã sắp xếp, chúng ta sử dụng std::lower_bound và std::upper_bound. lower_bound(value) trả về iterator tới phần tử đầu tiên >= value. upper_bound(value) trả về iterator tới phần tử đầu tiên > value. Số lượng phần tử bằng value trong phạm vi là khoảng cách giữa upper_bound và lower_bound.
8. Cộng số lượng này vào tổng đếm cuối cùng.
C++ Code Implementation (Đếm số lượng):

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm> // For std::sort, std::lower_bound, std::upper_bound
#include <cmath>

using namespace std;

// Function to generate all possible subset sums recursively
// start: starting index for this half
// end: ending index for this half
// arr: the original array
// current_sum: the sum of elements included so far
// sums: vector to store generated sums
void generate_subset_sums(int start, int end, const vector<int>& arr, long long current_sum, vector<long long>& sums) {
    // Base case: if we have considered all elements in this half
    if (start > end) {
        sums.push_back(current_sum);
        return;
    }

    // Recursive step 1: exclude the current element
    generate_subset_sums(start + 1, end, arr, current_sum, sums);

    // Recursive step 2: include the current element
    generate_subset_sums(start + 1, end, arr, current_sum + arr[start], sums);
}

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

    int n;
    long long k;
    cin >> n >> k;

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

    // Split the array into two halves
    int mid = n / 2;

    vector<long long> sums1;
    vector<long long> sums2;

    // Generate subset sums for the first half
    generate_subset_sums(0, mid - 1, arr, 0, sums1);

    // Generate subset sums for the second half
    generate_subset_sums(mid, n - 1, arr, 0, sums2);

    // Sort sums2 for efficient counting
    sort(sums2.begin(), sums2.end());

    // Count pairs of sums (s1 from sums1, s2 from sums2) such that s1 + s2 = k
    long long count = 0;
    for (long long s1 : sums1) {
        // We need s2 = k - s1. Count occurrences of k - s1 in sums2.
        long long target_s2 = k - s1;

        // Find the range of elements equal to target_s2 in sums2
        auto lower = lower_bound(sums2.begin(), sums2.end(), target_s2);
        auto upper = upper_bound(sums2.begin(), sums2.end(), target_s2);

        // The number of occurrences is the distance between upper_bound and lower_bound
        count += (upper - lower);
    }

    cout << count << endl;

    return 0;
}

Giải thích Code:
- Phần sinh tổng con (generate_subset_sums) và chia mảng giống hệt ví dụ 1.
- Vector sums1 và sums2 vẫn chứa tất cả các tổng con từ hai nửa.
- sort(sums2.begin(), sums2.end()): Bước sắp xếp sums2 vẫn cần thiết cho việc sử dụng lower_bound và upper_bound.
- Biến count kiểu long long được khởi tạo để lưu trữ tổng số tập con, vì số lượng có thể rất lớn (lên tới 2^40).
- Duyệt qua từng tổng s1 trong sums1.
- Tính target_s2 = k - s1.
- lower_bound(sums2.begin(), sums2.end(), target_s2): Tìm iterator đến vị trí đầu tiên trong sums2 không nhỏ hơn target_s2.
- upper_bound(sums2.begin(), sums2.end(), target_s2): Tìm iterator đến vị trí đầu tiên trong sums2 lớn hơn target_s2.
- Hiệu upper - lower chính là số lượng phần tử trong sums2 có giá trị đúng bằng target_s2.
- Số lượng này được cộng vào count.
- Sau khi duyệt hết sums1, count sẽ chứa tổng số cặp (s1, s2) thỏa mãn, chính là tổng số tập con của mảng gốc có tổng bằng K.
- In kết quả count.

Các biến thể và lưu ý

Bài toán khác: Kỹ thuật MITM không chỉ áp dụng cho bài toán tổng con. Nó có thể được dùng cho các bài toán khác liên quan đến chọn tập con, phân chia, hoặc tìm kiếm cặp kết hợp từ hai nửa. Ví dụ: tìm tập con có tổng gần K nhất, tìm cặp phần tử từ hai tập hợp có tổng bằng K, bài toán chia đồ vật vào hai túi sao cho hiệu trọng lượng nhỏ nhất, v.v.
Độ phức tạp không gian: Nhớ rằng MITM đòi hỏi không gian O(2^(N/2)). Nếu N quá lớn (ví dụ > 45-50), 2^(N/2) có thể vượt quá bộ nhớ cho phép.
Chia không đều: Đôi khi, việc chia mảng không cần chính xác là N/2. Tùy thuộc vào bài toán, có thể chia thành hai nửa có kích thước hơi khác nhau (ví dụ: N/2 và N - N/2) để tối ưu một chút hoặc để xử lý số lẻ N.
Kỹ thuật kết hợp: Bước "gặp gỡ ở giữa" không nhất thiết lúc nào cũng là sắp xếp + tìm kiếm nhị phân. Với một số bài toán, kỹ thuật two pointers trên hai danh sách đã sắp xếp có thể hiệu quả hơn hoặc đơn giản hơn. Ví dụ, nếu bạn cần tìm cặp s1, s2 sao cho s1 + s2 = K, bạn có thể sắp xếp cả sums1 và sums2, sau đó dùng two pointers: một con trỏ ở đầu sums1, một con trỏ ở cuối sums2, di chuyển chúng dựa vào tổng s1 + s2 so với K.
Dữ liệu đầu vào: MITM hoạt động tốt nhất khi các phần tử của mảng có thể kết hợp tuyến tính (ví dụ: tổng, hiệu, XOR). Nếu sự kết hợp phức tạp hơn, việc áp dụng MITM có thể khó khăn.

Bài tập ví dụ:

Độ đẹp nhân đôi

Trong một dự án nghiên cứu mới, FullHouse Dev đang tìm hiểu về các thuật toán tối ưu hóa mảng. Họ đặc biệt quan tâm đến việc làm thế nào để tối đa hóa "độ đẹp" của một mảng thông qua các phép biến đổi.

Bài toán

Cho một mảng \(A\) có độ dài \(n\). Bạn có thể chọn \(k\) chỉ số khác nhau và nhân đôi giá trị của phần tử tại các vị trí đó.

Độ đẹp của mảng được định nghĩa là tổng của bất kỳ mảng con nào có độ dài \(m\). Hãy tìm độ đẹp lớn nhất có thể đạt được sau khi hoán vị mảng \(A\).

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 hai số nguyên \(n\) và \(k\).
Dòng thứ hai của mỗi test case chứa \(n\) số nguyên, biểu diễn các phần tử của mảng.

OUTPUT FORMAT:

Với mỗi test case, in ra độ đẹp lớn nhất có thể đạt được sau khi hoán vị mảng \(A\).

Ràng buộc:

\(1 \leq T \leq 10^5\)
\(1 \leq n \leq 2 \times 10^5\)
\(1 \leq k, m \leq n\)
\(1 \leq A_i \leq 10^9\)

Ví dụ

INPUT

OUTPUT

16
10

Giải thích

Ở test case đầu tiên, ta có thể chọn các chỉ số 1, 2 và 3 (đánh số từ 1). Mảng \(A\) trở thành \([2,8,2,3,1]\). Hoán vị tạo ra độ đẹp lớn nhất là \([8,3,2,2,1]\). Do đó, đáp án là 16.
Ở test case thứ hai, ta có thể chọn chỉ số 1. Mảng \(A\) trở thành \([4,5,1]\). Hoán vị tạo ra độ đẹp lớn nhất là \([5,4,1]\). Do đó, đáp án là 10. Tuyệt vời! Đây là hướng dẫn giải bài "Độ đẹp nhân đôi" một cách ngắn gọn bằng C++ mà không cung cấp code hoàn chỉnh:

Hiểu bài toán: Mục tiêu cuối cùng là tối đa hóa tổng của m phần tử lớn nhất trong mảng SAU KHI bạn đã chọn k phần tử để nhân đôi giá trị của chúng và SAU KHI bạn có thể hoán vị mảng một cách tùy ý.
Phân tích phép biến đổi:
- Nhân đôi k phần tử: Bạn có thể chọn k CHỈ SỐ khác nhau trong mảng ban đầu để nhân đôi giá trị tại đó.
- Hoán vị mảng: Sau khi nhân đôi, bạn có thể sắp xếp lại các phần tử trong mảng mới theo bất kỳ thứ tự nào.
Tác động của Hoán vị: Khả năng hoán vị tùy ý có nghĩa là "độ đẹp lớn nhất" (tổng của một mảng con con độ dài m) chính là tổng của M phần tử có giá trị lớn nhất trong mảng SAU KHI đã thực hiện phép nhân đôi. Thứ tự của các phần tử chỉ quan trọng để gom m phần tử lớn nhất lại cạnh nhau, còn tổng của chúng thì không phụ thuộc thứ tự.
Quyết định quan trọng: Chọn k phần tử nào để nhân đôi? Để tối đa hóa tổng của M phần tử lớn nhất trong mảng kết quả, bạn nên làm cho các giá trị trong mảng kết quả trở nên lớn nhất có thể, đặc biệt là các giá trị lớn. Với các số nguyên dương, việc nhân đôi một giá trị sẽ làm tăng giá trị đó. Để tối đa hóa các giá trị, chiến lược tốt nhất là nhân đôi K phần tử có giá trị LỚN NHẤT trong mảng ban đầu. Việc chọn chỉ số nào không quan trọng bằng việc giá trị tại chỉ số đó là bao nhiêu, vì bạn có thể hoán vị sau đó. Chọn chỉ số có giá trị lớn để nhân đôi sẽ tạo ra giá trị 2 * (giá trị lớn) lớn hơn so với 2 * (giá trị nhỏ).
Thuật toán:
- Đọc n, k, m và các phần tử của mảng A.
- Sắp xếp mảng A theo thứ tự GIẢM DẦN. Lúc này, A[0], A[1], ..., A[n-1] lần lượt là các phần tử từ lớn nhất đến nhỏ nhất của mảng gốc.
- Các phần tử lớn nhất trong mảng gốc là A[0], A[1], ..., A[k-1]. Đây là các phần tử mà ta NÊN nhân đôi để tối đa hóa các giá trị.
- Tạo một danh sách/mảng mới chứa các giá trị sau khi nhân đôi:
  - Với i từ 0 đến k-1, thêm 2 * A[i] vào danh sách mới.
  - Với i từ k đến n-1, thêm A[i] (các phần tử còn lại, không được nhân đôi) vào danh sách mới.
- Lúc này, bạn có một danh sách chứa n giá trị là kết quả của việc nhân đôi k phần tử lớn nhất và giữ nguyên n-k phần tử còn lại.
- Sắp xếp danh sách mới này theo thứ tự GIẢM DẦN.
- Tổng của M phần tử đầu tiên trong danh sách đã sắp xếp này chính là độ đẹp lớn nhất có thể đạt được. Tính tổng này và in ra.
Lưu ý cài đặt:
- Sử dụng kiểu dữ liệu long long cho tổng để tránh tràn số, vì các giá trị có thể lên tới 10^9 và được nhân đôi.
- Sử dụng hàm sắp xếp có sẵn trong thư viện chuẩn (ví dụ: std::sort với std::greater hoặc sắp xếp giảm dần thủ công).
- Độ phức tạp thời gian chính là do sắp xếp, O(N log N) cho mỗi test case. Do tổng N qua các test case được giới hạn, giải pháp này hiệu quả.

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

Comments

There are no comments at the moment.