Hiểu bài toán

Bài toán yêu cầu tìm chi phí tối thiểu để mua đúng N bánh trung thu từ M loại bánh. Mỗi loại bánh i có giá mỗi chiếc là Ai và số lượng sẵn có là Bi. Ta cần mua tổng cộng N bánh sao cho tổng chi phí là nhỏ nhất. Cách tiếp cận tự nhiên là ưu tiên mua những loại bánh có giá rẻ nhất trước.

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

Cách Sắp xếp nổi bọt (Bubble Sort)

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

const long maxm = 1000005;
long a[maxm], b[maxm];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    freopen("mooncake.inp" , "r" , stdin);
    freopen("mooncake.out" , "w" , stdout);
    long n, m;
    cin >> n >> m;
    for (long i = 0; i < m; i++) {
        cin >> a[i] >> b[i];
    }
    for (long i = 0; i < m-1; i++) {
        for (long j = 0; j < m - 1 - i; j++) {
            if (a[j] > a[j+1]) {
                swap(a[j], a[j+1]);
                swap(b[j], b[j+1]);
            }
        }
    }
    long total_cost = 0;
    for (long i = 0; i < m && n > 0; i++) {
        long take = min(b[i], n);
        total_cost += take * a[i];
        n -= take;
    }
    cout << total_cost << "\n";
    return 0;
}

• Time Complexity: O(M^2)
• Space Complexity: O(M)

Phương pháp này sử dụng thuật toán sắp xếp nổi bọt (Bubble Sort) để sắp xếp các loại bánh theo giá tăng dần. Sau đó, nó lặp qua danh sách đã sắp xếp và mua bánh từ loại rẻ nhất cho đến khi đủ N chiếc. Bubble Sort có độ phức tạp O(M^2), không hiệu quả với M lớn (ví dụ M = 10^5).

Cách Sắp xếp với std::sort

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ifstream fin("MOONCAKE.INP");
    ofstream fout("MOONCAKE.OUT");
    long long N;
    int M;
    fin >> N >> M;
    vector<pair<long long,long long>> f(M);
    for(int i=0;i<M;i++) fin >> f[i].first >> f[i].second;
    sort(f.begin(), f.end());
    long long total = 0;
    for(int i=0;i<M && N>0;i++){
        long long take = min(f[i].second, N);
        total += take * f[i].first;
        N -= take;
    }
    fout << total << "\n";
}

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

Đây là phương pháp tối ưu. Ta sử dụng cấu trúc dữ liệu vector và hàm sort của thư viện chuẩn C++ để sắp xếp các cặp (giá, số lượng) theo giá tăng dần. Độ phức tạp sắp xếp là O(M log M). Sau đó, ta duyệt mảng và mua bánh theo greedy. Đây là cách làm hiệu quả và phổ biến nhất.

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

Bài học kinh nghiệm

• Bài toán có tính chất greedy: luôn ưu tiên mua loại bánh có đơn giá thấp nhất để tiết kiệm chi phí.
• Sau khi sắp xếp theo đơn giá tăng dần, việc lựa chọn trở nên đơn giản: chỉ cần mua hết số lượng của loại bánh rẻ nhất, nếu vẫn chưa đủ thì sang loại tiếp theo.

Lỗi thường gặp

• Sử dụng thuật toán sắp xếp kém hiệu quả (như Bubble Sort) dẫn đến Time Limit Exceeded (TLE) khi M lớn.
• Quên sử dụng kiểu dữ liệu lớn (long long) cho tổng chi phí và số lượng bánh, dẫn đến tràn số (overflow) nếu các giá trị đầu vào lớn.