Hiểu bài toán

Bài toán yêu cầu tính số tiền tối thiểu cần bỏ ra để mua hết n mặt hàng với giá c_i. Khuyến mại áp dụng là mua 3 mặt hàng sẽ được miễn phí 1 mặt hàng có giá cao nhất trong 3 mặt hàng đó. Để tổng chi phí là nhỏ nhất, ta cần mặt hàng được miễn phí có giá trị càng lớn càng tốt. Do đó, chiến lược tối ưu là sắp xếp các mặt hàng theo giá giảm dần và chọn những mặt hàng có giá lớn nhất (cứ 3 mặt hàng mua thì 1 mặt hàng đầu tiên trong danh sách sắp xếp giảm dần được miễn phí).

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

Cách Sắp xếp giảm dần và trừ đi các mặt hàng được miễn phí

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, a[1000011], s = 0;
int main() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        s += a[i];
    }
    sort(a + 1, a + n + 1, greater<ll>());
    for (ll i = 1; i <= n / 3; i++) {
        s -= a[i];
    }
    cout << s;
}

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

Cách tiếp cận này dựa trên việc tối ưu hóa giá trị được miễn phí. Bước 1: Tính tổng chi phí giả định là tổng tất cả các giá (s). Bước 2: Sắp xếp mảng giá giảm dần. Bước 3: Với mỗi nhóm 3 mặt hàng, ta sẽ được miễn phí 1 mặt hàng. Vì muốn tổng tiền phải trả là nhỏ nhất, ta cần 'hy sinh' những mặt hàng có giá trị lớn nhất. Trong mảng đã sắp xếp giảm dần, các phần tử đầu tiên là các phần tử lớn nhất. Vì vậy, ta chỉ cần lấy n/3 phần tử đầu tiên (tương ứng với số lần miễn phí) và trừ chúng khỏi tổng chi phí ban đầu.

Cách Sắp xếp tăng dần và chọn từ cuối

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[1000011], n, s = 0;

int main() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        s += a[i];
    }
    ll x = n / 3;
    sort(a + 1, a + n + 1);
    ll i = n;
    while (x--) {
        s -= a[i];
        i--;
    }
    cout << s;
    return 0;
}

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

Cách tiếp cận này tương tự cách 1 nhưng sử dụng thứ tự sắp xếp khác. Bước 1: Tính tổng s. Bước 2: Sắp xếp mảng tăng dần. Bước 3: Duyệt từ cuối mảng (phần tử lớn nhất) về đầu, lấy đúng n/3 phần tử lớn nhất để trừ vào tổng. Logic là相同的: chọn các phần tử có giá trị lớn nhất để được miễn phí.

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

Bài học kinh nghiệm

• Để giảm thiểu chi phí, ta cần tối đa hóa giá trị số tiền được giảm. Vì được giảm giá của mặt hàng đắt nhất trong mỗi nhóm mua 3, ta cần tập trung các mặt hàng đắt nhất vào các nhóm này.
• Sau khi sắp xếp các giá trị giảm dần, các phần tử đầu tiên là các phần tử lớn nhất. Ta chỉ cần loại bỏ n/3 phần tử đầu tiên khỏi tổng giá trị ban đầu.

Lỗi thường gặp

• Việc sắp xếp mảng không đúng thứ tự (tăng dần thay vì giảm dần) nếu không đi kèm logic lấy phần tử từ cuối mảng sẽ dẫn đến sai sót.
• Quên khai báo biến tổng là kiểu dữ liệu lớn (long long) để tránh tràn số khi n và ci lớn (nên nhớ ci lên tới 10^9 và n có thể lên tới 10^5).