Hiểu bài toán

Bài toán yêu cầu tìm số tiền tối thiểu cần trả để mua n cuốn sách với giá cho trước, áp dụng chương trình khuyến mãi 'mua 3 lấy 2 quyển đắt hơn'. Tức là với mỗi nhóm 3 quyển sách bất kỳ, quyển rẻ nhất trong nhóm sẽ được miễn phí. Người mua có thể chia sách thành các nhóm khác nhau để tối ưu hóa chi phí. Để trả ít tiền nhất, ta cần tối đa hóa tổng giá trị của các cuốn sách được miễn phí. Điều này có nghĩa là trong mỗi nhóm 3 sách, ta muốn quyển rẻ nhất có giá trị cao nhất có thể. Do đó, ta nên chia nhóm sao cho các nhóm chứa các cuốn sách đắt tiền nhất có thể.

Các cách tiếp cận

Cách Sắp xếp giảm dần và loại bỏ

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    // Sắp xếp giảm dần
    sort(a.begin(), a.end(), greater<int>());
    long long total_cost = 0;
    // Vòng lặp qua các sách đã sắp xếp
    for (int i = 0; i < n; i++) {
        // Nếu vị trí là 0, 1, 4, 5, 7, 8,... (tức là không phải 2, 5, 8,...)
        // Tức là các vị trí index % 3 != 2
        if (i % 3 != 2) {
            total_cost += a[i];
        }
    }
    cout << total_cost;
    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Đây là cách tiếp cận trực quan nhất và cũng là cách được sử dụng trong các giải pháp mẫu.

1. Sắp xếp: Đầu tiên, ta sắp xếp mảng giá sách theo thứ tự giảm dần. Mục đích là để đưa những cuốn sách đắt tiền nhất lên đầu.
2. Chia nhóm: Ta lần lượt duyệt qua các cuốn sách đã sắp xếp. Để tối đa hóa giá trị miễn phí, ta cần đảm bảo rằng trong mỗi nhóm 3 sách, quyển được miễn phí (có giá trị thấp nhất trong nhóm) là đắt nhất có thể. Bằng cách sắp xếp giảm dần và chia nhóm liên tiếp:
   • Nhóm 1: Sách ở index 0, 1, 2. Sách index 2 được miễn phí.
   • Nhóm 2: Sách ở index 3, 4, 5. Sách index 5 được miễn phí.
   • ... Như vậy, các sách được miễn phí sẽ là những sách ở các vị trí có chỉ số i chia hết cho 3 (tính từ 0).
3. Tính tổng: Chỉ cộng dồn giá trị của những cuốn sách không bị miễn phí (tức là những cuốn ở vị trí i không chia hết cho 3).

Ví dụ với [10, 9, 6, 4, 4, 3, 2]:

• Index 0 (10), 1 (9) -> Trả tiền.
• Index 2 (6) -> Miễn phí.
• Index 3 (4), 4 (4) -> Trả tiền.
• Index 5 (3) -> Miễn phí.
• Index 6 (2) -> Trả tiền. Tổng = 10 + 9 + 4 + 4 + 2 = 29.

Cách Quy hoạch động (Khác biệt)

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    // Sắp xếp giảm dần
    sort(a.begin(), a.end(), greater<int>());

    // dp[i] là chi phí tối thiểu khi mua i cuốn sách đầu tiên
    vector<long long> dp(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        // Truong hop mua them 1 cuon
        dp[i] = dp[i-1] + a[i-1];

        // Truong hop mua them 3 cuon (neu co du)
        if (i >= 3) {
            // Khi mua them 3 cuon, cuon thu i-2 (gia tri nho nhat trong 3 cuon) duoc mien phi
            // Chi phi truoc do la dp[i-3]
            // Chi phi them la a[i-1] + a[i-2] (vi a[i-3] duoc mien phi)
            dp[i] = min(dp[i], dp[i-3] + a[i-1] + a[i-2]);
        }
    }

    cout << dp[n];
    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Cách tiếp cận này sử dụng quy hoạch động để đảm bảo luôn tìm được cách chia nhóm tối ưu.

1. Sắp xếp: Vẫn phải sắp xếp giảm dần. Điều này đảm bảo rằng khi xét 3 cuốn sách liên tiếp trong mảng đã sắp xếp, cuốn ở vị trí thấp nhất (bị loại) có giá trị cao nhất có thể so với việc lấy các cuốn không liên tiếp.
2. Định nghĩa DP: dp[i] là số tiền phải trả tối thiểu để mua i cuốn sách đầu tiên trong danh sách đã sắp xếp.
3. Công thức truy hồi:
   • Khi mua thêm 1 cuốn, ta không được giảm giá. Cost = dp[i-1] + a[i-1].
   • Khi mua thêm 3 cuốn (từ i-3 lên i), ta được miễn phí cuốn thứ i-2 (vì đang xét giảm dần, a[i-1] và a[i-2] là 2 cuốn đắt nhất trong 3 cuốn này). Cost = dp[i-3] + a[i-1] + a[i-2].
   • Chọn giá trị nhỏ hơn giữa hai trường hợp.
4. Độ phức tạp: O(n log n) do sắp xếp và O(n) cho DP. Giải pháp này đúng đắn về mặt lý thuyết cho mọi cách chia nhóm, nhưng với ràng buộc của bài toán (miễn phí cuốn rẻ nhất trong nhóm), việc sắp xếp giảm dần và chia nhóm liên tiếp đã là tối ưu, biến quy hoạch động thành một cách tiếp cận 'overkill' nhưng vẫn đúng.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Để trả ít tiền nhất, ta cần tối đa hóa giá trị của các cuốn sách được miễn phí.
• Việc sắp xếp giá giảm dần và chia nhóm 3 liên tiếp (bỏ qua mỗi cuốn thứ 3) chính là chiến lược tối ưu, không cần dùng đến quy hoạch động hay các thuật toán phức tạp hơn.
• Bài toán quy về việc chỉ cần cộng dồn các giá trị tại các vị trí index không chia hết cho 3 trong mảng đã sắp xếp giảm dần.

Lỗi thường gặp

• Sai lệch trong chỉ số (Indexing Off-by-one): Các giải pháp mẫu có sự khác biệt nhỏ về chỉ số (dùng i%3 hoặc (i+1)%3). Quan trọng là phải nhất quán logic của mình. Nếu dùng i từ 0, ta thường bỏ qua i%3 == 2. Nếu dùng i từ 1, ta thường bỏ qua i%3 == 0.
• Kiểu dữ liệu tổng tiền: Tổng tiền có thể lên tới ~10^5 * 10^6 = 10^11, vượt quá giới hạn củaint(2*10^9). Cần dùnglong long(hoặcunsigned long long`) để lưu trữ kết quả.
• Trình tự sắp xếp: Luôn luôn phải sắp xếp giảm dần. Nếu sắp xếp tăng dần, logic chia nhóm sẽ bị sai và kết quả không tối ưu.