Hướng dẫn giải của Mua 4 tặng 1


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, God_Of_Sever, vuquochiep, quanghuy123

Hiểu bài toán

Bài toán yêu cầu tính tổng số tiền tối thiểu cần bỏ ra để mua N mặt hàng với giá trị c_i. Trong chương trình khuyến mãi 'mua 4 tặng 1', cứ sau khi mua 4 mặt hàng bất kỳ, ta sẽ được giảm giá cho mặt hàng có giá trị cao nhất trong nhóm 4 mặt hàng đó. Để giảm chi phí nhiều nhất, ta cần tối ưu hóa việc chọn các mặt hàng được miễn phí. Cụ thể, ta nên chọn các mặt hàng có giá trị cao nhất để làm mặt hàng được tặng. Nói cách khác, ta cần chia N mặt hàng thành các nhóm (mỗi nhóm 5 mặt hàng: 4 trả tiền + 1 miễn phí), trong đó mặt hàng miễn phí là mặt hàng có giá trị cao nhất trong nhóm.

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

Cách Giả lập
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> c(n);
    long long total_sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> c[i];
        total_sum += c[i];
    }
    // Sắp xếp giảm dần để dễ dàng chọn các phần tử lớn nhất
    sort(c.rbegin(), c.rend());

    long long discount = 0;
    // Vòng lặp này tính tổng giá trị các mặt hàng được miễn phí
    // Các mặt hàng được miễn phí là các phần tử có chỉ số 0, 5, 10, ...
    // Tuy nhiên, do ta sắp xếp giảm dần, các phần tử này chính là các phần tử lớn nhất trong các nhóm 5
    // Thực tế, trong cách giải Sort và Chia nhóm, ta chỉ cần lấy tổng các phần tử đầu tiên của mỗi nhóm 5
    // Nhưng do đã sort giảm dần, ta chỉ cần lặp và lấy các phần tử tại vị trí 0, 5, 10...
    // Hoặc đơn giản hơn là lấy tổng các phần tử tại vị trí (i*5) với i từ 0...
    // Lưu ý: Với N=5, ta được miễn phí phần tử c[0] (lớn nhất).
    // Với N=10, ta được miễn phí c[0] và c[5].
    // Tuy nhiên, có một cách tiếp cận khác: Tổng tiền = Tổng tất cả - Tổng các mặt hàng miễn phí.
    // Trong giải pháp được cung cấp, họ sort giảm dần và trừ đi các phần tử đầu tiên.
    // Điều này tương đương với việc miễn phí các mặt hàng có giá trị lớn nhất.
    // Ta sẽ mô phỏng theo cách này.

    // Giải pháp tối ưu:
    // Sắp xếp giảm dần.
    // Các mặt hàng được miễn phí nằm ở các vị trí 0, 1, 2, ..., (n/5 - 1) trong mảng đã sort?
    // Không. Ví dụ: 5 items: [10, 8, 7, 5, 3]. Sort: [10, 8, 7, 5, 3]. 
    // Nếu ta chia nhóm 5: [10, 8, 7, 5, 3] -> Miễn phí 10. Trả 8+7+5+3=23.
    // Nếu ta chia nhóm không đúng cách? Ví dụ: 6 items. [12, 10, 8, 7, 5, 3].
    // Nhóm 1: [12, 10, 8, 7] -> Miễn phí 12. Nhóm 2: [5, 3] -> không đủ 4 => trả cả.
    // Tổng: (10+8+7) + (5+3) = 25 + 8 = 33. Trừ 12 => 21? Sai. 10+8+7+5+3 = 33. Trừ 12 => 21.
    // Thực tế: Ta phải mua 6 món. Chọn 4 món đắt nhất (12, 10, 8, 7) để được giảm 12. Trả 10+8+7=25.
    // Món còn lại (5) và (3) trả full. Tong = 25+5+3 = 33. 
    // Wait, bài toán là 'Mua 4 tặng 1'. Cứ mua 4 mặt hàng, tặng 1.
    // Để tối ưu, ta nên gom các mặt hàng đắt nhất vào các nhóm 5.
    // Nhóm 1 (5 items): [12, 10, 8, 7, 5] -> Miễn phí 12. Trả 10+8+7+5 = 30.
    // Nhóm 2 (1 item): [3] -> Trả 3.
    // Tổng = 33.
    // Hay: [12, 10, 8, 7] + [5, 3] -> Miễn phí 12. Trả 10+8+7+5+3 = 33.
    // Vấn đề nằm ở logic 'Cứ mua 4 mặt hàng'.
    // Giả sử ta có 5 items: [1, 2, 3, 4, 100].
    // Mua [100, 4, 3, 2] -> Miễn phí 100. Trả 4+3+2=9. Mua [1] -> Trả 1. Tong=10.
    // Mua [1, 2, 3, 4] -> Miễn phí 4. Trả 1+2+3=6. Mua [100] -> Trả 100. Tong=106.
    // Rõ ràng phải chọn nhóm đắt nhất.
    // Thuật toán đúng: Sắp xếp giảm dần. 
    // Với N items, ta có thể tạo ra k = N/5 nhóm hoàn chỉnh (5 items/group).
    // Các mặt hàng còn lại (r items) không tạo được nhóm hoàn chỉnh => trả full.
    // Trong các nhóm hoàn chỉnh, ta được miễn phí item đắt nhất trong nhóm đó.
    // Để tối ưu, ta cần các item được miễn phí là các item có giá trị cao nhất.
    // Vậy, ta cần chia N items thành: 
    // - r items cuối (giá trị thấp nhất) => trả full.
    // - N-r items còn lại (giá trị cao hơn) => chia thành các nhóm 5.
    // Trong mỗi nhóm 5, ta được miễn phí item đắt nhất.
    // Do các items đã được sort giảm dần, các items đắt nhất nằm ở đầu.
    // Nếu ta có k nhóm hoàn chỉnh, k = floor((N-r)/5) ??? Không.
    // Logic thực tế:
    // Số lượng mặt hàng được miễn phí = floor(N/5).
    // Để tối đa hóa giá trị được miễn phí, ta chọn các mặt hàng có giá trị cao nhất.
    // Vậy: Sắp xếp giảm dần. Lấy tổng các phần tử từ index 0 đến index (N/5 - 1).
    // Đây là tổng giá trị được miễn phí.
    // Kết quả = Tổng tất cả - Tổng các phần tử đầu.
    // Ví dụ: N=5, sort: [10, 8, 7, 5, 3]. N/5 = 1. Miễn phí index 0 (10). Trả 23. Đúng.
    // Ví dụ: N=6, sort: [12, 10, 8, 7, 5, 3]. N/5 = 1. Miễn phí index 0 (12). Trả 10+8+7+5+3=33. Đúng.
    // Ví dụ: N=10, sort: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. N/5 = 2. Miễn phí index 0 (10) và index 1 (9).
    // Trả: 1+2+3+4+5+6+7+8 = 36. 
    // Kiểm tra: Nhóm 1: [10, 8, 7, 6, 5] -> trả 8+7+6+5=26. Nhóm 2: [4, 3, 2, 1] -> không đủ 4? 
    // Chờ đã, nếu có 10 items, ta có 2 nhóm hoàn chỉnh 5 items.
    // Nhóm 1: 10, 9, 8, 7, 6 -> Miễn phí 10. Trả 9+8+7+6=30.
    // Nhóm 2: 5, 4, 3, 2, 1 -> Miễn phí 5. Trả 4+3+2+1=10. Tong=40.
    // Công thức: Tong = (10+9+8+7+6+5+4+3+2+1) - (10+5) = 55 - 15 = 40. Đúng.
    // Vậy thuật toán là: Sort giảm dần, trừ đi tổng N/5 phần tử đầu tiên.

    long long num_free = n / 5;
    long long discount_amount = 0;
    for (int i = 0; i < num_free; ++i) {
        discount_amount += c[i];
    }

    cout << total_sum - discount_amount << endl;
    return 0;
}
  • Time Complexity: O(N log N)
  • Space Complexity: O(N)

Đây là cách tiếp cận trực tiếp nhất dựa trên quan sát toán học. Sau khi sắp xếp các giá trị giảm dần, các mặt hàng có khả năng được miễn phí cao nhất chính là các mặt hàng ở đầu danh sách. Số lượng mặt hàng được miễn phí là N/5. Do đó, ta chỉ cần trừ đi tổng giá trị của N/5 mặt hàng đắt nhất từ tổng giá trị ban đầu.

Cách Quy hoạch động
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> c(n);
    for (int i = 0; i < n; ++i) {
        cin >> c[i];
    }
    // Sắp xếp tăng dần để tiện cho việc DP
    sort(c.begin(), c.end());

    // dp[i] là chi phí tối thiểu để mua i mặt hàng đầu tiên (từ nhỏ đến lớn)
    // Tuy nhiên, việc này hơi phức tạp do điều kiện 'mua 4 tặng 1'.
    // Ta có thể dùng DP dạng:
    // dp[i] = chi phí tối thiểu để mua i mặt hàng.
    // Chuyển trạng thái:
    // 1. Mua mặt hàng i không được miễn phí: dp[i] = dp[i-1] + c[i-1]
    // 2. Mua mặt hàng i được miễn phí (tức là thuộc nhóm 5): 
    //    Nếui là phần tử lớn nhất trong nhóm, ta không trả tiền cho nó.
    //    Nhưng DP thông thường sẽ khó xử lý việc 'tặng' này vì nó liên quan đến giá trị.

    // Có một cách DP khác:
    // Sắp xếp giảm dần. dp[i] là chi phí tối thiểu cho i items đầu tiên.
    // dp[i] = min(dp[i-1] + c[i-1], dp[i-5] + (tổng 4 items lớn nhất trong nhóm 5))
    // Nhưng c[i-1] là item nhỏ nhất trong i items đầu tiên.
    // Nếu ta chia nhóm 5: [c[0], c[1], c[2], c[3], c[4]]. Miễn phí c[0].
    // Chi phí cho 5 items này: c[1]+c[2]+c[3]+c[4].
    // Công thức DP:
    // dp[i] = min( dp[i-1] + c[i-1], dp[i-5] + (c[i-2] + c[i-3] + c[i-4] + c[i-5]) ) 
    // Lưu ý: c[] đã sort giảm dần.
    // dp[0] = 0.
    // i chạy từ 1 đến n.
    // Với i < 5, không thể có free => dp[i] = dp[i-1] + c[i-1].
    // Với i >= 5: 
    //    Option 1: Item c[i-1] không được free. Chi phí = dp[i-1] + c[i-1].
    //    Option 2: Item c[i-1] được free. Điều này có nghĩa là c[i-1] là phần tử lớn nhất trong 1 nhóm 5.
    //    Nhóm 5 bao gồm: c[i-1], c[i-2], c[i-3], c[i-4], c[i-5].
    //    (Lưu ý: c[i-1] là item nhỏ nhất trong đoạn này nếu sort giảm dần? Không, c[0] là lớn nhất).
    //    Nếu sort giảm dần: c[0] >= c[1] >= ... >= c[n-1].
    //    Nếu ta xét dp[i] cho i items đầu (c[0]...c[i-1]).
    //    Nếu item c[i-1] được free, nó phải là phần tử lớn nhất trong 1 nhóm.
    //    Nhưng c[i-1] là phần tử nhỏ nhất trong đoạn đang xét. 
    //    VẬY KHÔNG ĐƯỢC. Item được free phải là phần tử lớn nhất.
    //    Do đó, DP cần xét theo chiều ngược lại hoặc thay đổi logic.

    // Thay đổi: Sắp xếp tăng dần. Càng về sau càng lớn.
    // dp[i] = chi phí cho i items đầu (nhỏ nhất).
    // Nếu xét item c[i-1] (lớn nhất trong i items đó).
    // Option 1: Không free c[i-1]. dp[i] = dp[i-1] + c[i-1].
    // Option 2: Free c[i-1]. Ta cần mua 4 items nhỏ hơn nó để tạo nhóm.
    //    Nhưng items nhỏ hơn nó là c[0]...c[i-2].
    //    Ta không thể ép buộc 4 items gần nhất (c[i-2]...c[i-5]) vào nhóm được vì có thể có cách chia khác tốt hơn.
    //    Tuy nhiên, để tối ưu, ta luôn muốn free item lớn nhất.
    //    Vậy nếu free c[i-1], ta phải chọn thêm 4 items từ phần còn lại.
    //    Câu hỏi là 4 items nào? 
    //    Logic thường dùng: DP[i] = min(DP[i-1] + c[i-1], DP[i-5] + sum(c[i-2]...c[i-5]))
    //    Nhưng điều này giả định rằng c[i-1] free và 4 items kia là 4 items liền trước.
    //    Liệu điều này có tối ưu? 
    //    Ví dụ: [1, 2, 3, 100, 101]. Sort tăng dần: [1, 2, 3, 100, 101].
    //    DP[5]: 
    //      Option 1 (không free 101): DP[4] + 101 = (1+2+3+100) + 101 = 207.
    //      Option 2 (free 101): DP[0] + (1+2+3+100) = 106.
    //    Kết quả đúng là 106 (mua 1,2,3,100 được free 101).
    //    Vậy DP[i] = min(DP[i-1] + c[i-1], DP[i-5] + sum(c[i-2]...c[i-5])) là đúng.
    //    Tại sao? Vì item c[i-1] là item lớn nhất trong tập hợp i items.
    //    Nếu ta free nó, ta cần mua thêm 4 items. Để tổng tiền thấp nhất, 4 items đó nên là 4 items nhỏ nhất có thể.
    //    Tuy nhiên, DP[i-5] + sum(c[i-2]...c[i-5]) đang chọn 4 items ngay trước nó.
    //    Liệu có thể chọn 4 items không liên tục? Ví dụ: [1, 10, 11, 12, 100].
    //    Free 100. Mua [1, 10, 11, 12]. Cost = 34.
    //    DP[5] = DP[0] + (1+10+11+12) = 34.
    //    Nếu có thêm item 13: [1, 10, 11, 12, 13, 100].
    //    Free 100. Mua [1, 10, 11, 12, 13].
    //    Có thể chia: [1, 10, 11, 12] free 12 (cost 1+10+11=22) + [13, 100] (cost 13+100=113) => 135.
    //    Hoặc: [1, 10, 11, 12, 13] free 13 (cost 1+10+11+12=34) + [100] (cost 100) => 134.
    //    Hoặc: [10, 11, 12, 13] free 13 (cost 10+11+12=33) + [1, 100] (cost 1+100=101) => 134.
    //    Hoặc: [1, 10, 11, 100] free 100 (cost 1+10+11=22) + [12, 13] (cost 12+13=25) => 47. -> Đây là best.
    //    DP[6] với logic 'liền trước': DP[1] + (10+11+12+13) = (1) + 46 = 47. 
    //    Chờ đã, DP[1] là cost của 1 item [1] = 1.
    //    DP[1] + (10+11+12+13) = 1 + 46 = 47.
    //    Logic này có vẻ đúng.
    //    Tại sao? Vì DP[i-5] là cost tối ưu của i-5 items nhỏ nhất.
    //    Sum(c[i-2]...c[i-5]) là 4 items lớn nhất tiếp theo sau i-5 items đó.
    //    Việc này tách biệt: Cost của i-5 items nhỏ nhất + Cost của 4 items lớn nhất tiếp theo (mà không được free).
    //    Đợi đã, nếu ta free item lớn nhất (c[i-1]), thì 4 items còn lại trong nhóm phải trả tiền.
    //    4 items đó là ai? Chúng ta muốn chúng nhỏ nhất có thể.
    //    Trong DP[i-5] + sum(c[i-2]...c[i-5]), 4 items đó là c[i-2], c[i-3], c[i-4], c[i-5].
    //    Đây là 4 items lớn nhất trong số i-1 items còn lại.
    //    Liệu có cách nào tốt hơn? 
    //    Giả sử ta free c[i-1]. Nhóm của nó là {c[i-1], x, y, z, w}.
    //    Cost = DP[rest] + x + y + z + w.
    //    Để minimize, x,y,z,w phải là 4 items lớn nhất trong rest? KHÔNG.
    //    Chúng phải là 4 items mà ta phải trả tiền.
    //    Để tối ưu, ta nên chọn 4 items nhỏ nhất trong rest? KHÔNG.
    //    Vì items nhỏ nhất có thể được dùng để 'che chắn' cho các items lớn khác được free.
    //    Ví dụ: [1, 2, 3, 4, 100, 101, 102, 103, 104, 105].
    //    Free 105. Nhóm: {105, 104, 103, 102, 101}. Cost = 104+103+102+101 = 410.
    //    Remaining: [1, 2, 3, 4, 100]. Cost = 1+2+3+4+100 = 110.
    //    Total = 520.
    //    Nếu chia khác: {105, 100, 4, 3, 2}. Cost = 100+4+3+2 = 109. Remaining: [1, 101, 102, 103, 104]. Cost = 1+101+102+103+104 = 411. Total = 520.
    //    Total same.
    //    Quy tắc là: Cost = Sum(all) - Sum(items free).
    //    DP[i] = Min(DP[i-1] + c[i-1], DP[i-5] + sum(c[i-2]...c[i-5])) là một cách viết lại của quy tắc này.
    //    Nó giả định rằng items free luôn là các items lớn nhất.
    //    Và items được free sẽ được nhóm với 4 items lớn nhất còn lại.
    //    Hay: items free là các items tại vị trí 0, 5, 10... (nếu sort giảm dần).
    //    Do đó, cách giải Sort và Trừ là chính xác và đơn giản nhất.
    //    DP là thừa thãi ở đây.

    // Tuy nhiên, để hoàn thiện giáo án, ta có thể trình bày DP.
    // DP[i]: chi phí tối thiểu để mua i mặt hàng đầu tiên trong mảng đã sort giảm dần.
    // dp[0] = 0;
    // for (int i = 1; i <= n; i++) {
    //     dp[i] = dp[i-1] + c[i-1]; // Mua thêm 1 item, không được free
    //     if (i >= 5) {
    //         // Thử chia 5 items cuối thành 1 nhóm: c[i-5],...,c[i-1]. Free c[i-5] (lớn nhất).
    //         // Cost 4 items còn lại: c[i-4]...c[i-1]
    //         // Cost = dp[i-5] + c[i-4] + c[i-3] + c[i-2] + c[i-1];
    //         // Lưu ý: c[] sort giảm dần. c[i-5] là lớn nhất trong đoạn.
    //         long long group_cost = c[i-4] + c[i-3] + c[i-2] + c[i-1];
    //         if (dp[i] > dp[i-5] + group_cost) dp[i] = dp[i-5] + group_cost;
    //     }
    // }
    // cout << dp[n];

    return 0;
}
  • Time Complexity: O(N log N) (do sort)
  • Space Complexity: O(N)

Sử dụng quy hoạch động để lựa chọn giữa việc mua thêm item không được giảm giá hoặc tạo thành nhóm 5 để được giảm giá 1 item. Tuy nhiên, so với phương pháp Greedy (Sort và trừ), DP có phần phức tạp hơn và kết quả tương đương. DP[i] = min(DP[i-1] + c[i-1], DP[i-5] + sum(c[i-2]...c[i-1])).

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

Cách tiếp cận Time Space Tên
1 O(N log N) O(N) Giả lập
2 O(N log N) (do sort) O(N) Quy hoạch động

Bài học kinh nghiệm

  • Để tối ưu hóa chi phí, ta cần tối đa hóa giá trị của các mặt hàng được miễn phí. Do đó, ta nên chọn các mặt hàng có giá trị cao nhất để được miễn phí.
  • Bài toán có tính chất Tham lam (Greedy): Sau khi sắp xếp giảm dần, các mặt hàng được miễn phí luôn nằm ở các vị trí cố định (0, 5, 10, ...) trong mảng đã sort.
  • Tổng số mặt hàng được miễn phí là N/5 (phép chia lấy nguyên).

Lỗi thường gặp

  • Lỗi tràn số (Integer Overflow): Tổng giá trị các mặt hàng có thể lên tới 10^5 * 10^9 = 10^14, nên cần sử dụng kiểu dữ liệu 64-bit (long long trong C++).
  • Sai logic về thứ tự miễn phí: Cố gắng miễn phí các mặt hàng giá trị thấp sẽ dẫn đến chi phí cao hơn.
  • Xử lý sai số lượng nhóm được khuyến mãi: N/5 phải là phép chia lấy nguyên.

Bình luận

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.