Mua sách

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
corona
Dạng bài
Điểm: 200 (p) Thời gian: 1.1s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một lời quảng cáo chào hàng trong một hiệu sách “mua 3, tặng 1, trả tiền 2”. Vì vậy, mỗi khách mua ba quyển sẽ được tặng một quyển có giá rẻ nhất trong ba quyển. Và tất nhiên, khách hàng có thể mua nhiều sách, phụ thuộc vào việc sắp xếp các quyển sách vào mỗi nhóm ba quyển để được miễn phí quyển có giá rẻ nhất trong nhóm đó.
Ví dụ, khách hàng lấy các quyển sách có giá 10, 3, 2, 4, 6, 4, 9. Nếu các quyển sách được sắp thành các nhóm: (10,3,2), (4,6,4) và (9) thì khách hàng ấy sẽ được tặng cuốn sách có giá là 2 trong nhóm một, 4 trong nhóm hai, và không có quyển sách nào được tặng trong nhóm ba vì nhóm này chỉ có 1 quyển.

Cô bán hàng là một người tốt bụng vì vậy cô ấy luôn muốn mỗi khách hàng trả ít tiền nhất có thể.

Yêu cầu: Cho giá các quyển sách, hãy giúp cô bán hàng sắp xếp các quyển sách vào các nhóm sao cho tổng số tiền khách hàng phải trả là ít nhất có thể. Chú ý cô bán hàng có thể sắp xếp các quyển sách vào các nhóm có ít nhất 1 quyển hoặc nhiều nhất 3 quyển.

Input

  • Dòng 1 gồm một số nguyên \(N (N ≤ 10^5)\) – là số sách khách hàng mua.
  • \(N\) dòng tiếp theo mỗi dòng ghi một số nguyên \(A_i (A_i ≤ 10^9)\) – là giá mỗi quyển sách. Các số trên một dòng của input file được ghi cách nhau bởi dấu cách.

Output

  • Ghi ra một số nguyên duy nhất là giá tiền nhỏ nhất mà khách hàng phải trả.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(N ≤ 2000\).
  • Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Example

Test 1

Input 
4
3
2
3
2
Output 
8

Test 1

Input 
6
6
4
5
5
5
5
Output 
21

Bình luận


  • 10
    SPyofgame    8:20 a.m. 17 Tháng 6, 2020 ← đã chỉnh sửa

    Spoiler Alert

    Approach

    • Sort giảm dần, lấy giá trị 2 cuốn rồi bỏ qua 1 cuốn

    Đề yêu cầu: Cứ mỗi cặp 3 số mình sẽ lấy số nhỏ nhất bỏ đi, còn lại là tính tổng

    Chứng minh: Cứ mỗi cặp \((a, b, c)\) và \((a \geq b \geq c)\) để mình lợi nhất thì \(c\) phải lớn nhất có thể. Mà nếu sắp xếp giảm dần thì mỗi cặp 3 số sẽ có \(c\) thỏa mãn

    Question

    • Liệu bài này có thể giải bằng quy hoạch động không ?

    Reference AC code | \(O(n\) \(log_2n)\) time | \(O(n)\) auxiliary space | Sorting, Greedy

    C++
    int main()
{
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a) cin >> x;
    sort(a.begin(), a.end(), greater<int>());

    ll res = 0;
    for (int i = 0; i < n; i += 3)
        res += a[i] + a[i + 1];

    cout << res;
    return 0;
}

    • 0
      lagiahuy    8:48 p.m. 9 Tháng 10, 2021

      vi a(n);
      vi là j thế!?


      • 4
        SPyofgame    10:05 p.m. 9 Tháng 10, 2021

        Mình vừa sửa rôì nhé, ôi trời ơi mấy cái sol chán ngắt cũ rích của mình


        • 2
          lagiahuy    9:08 a.m. 11 Tháng 10, 2021

          ôk rồi đó bạn

      2 bình luận nữa