Hiểu bài toán

Bài toán yêu cầu tìm cách chọn thứ tự vắt sữa tối ưu cho n con bò để tối đa hóa tổng số sữa thu được. Ban đầu, mỗi con bò i có sản lượng a[i]. Khi vắt sữa một con bò, tất cả những con bò chưa được vắt sẽ bị giảm sản lượng đi 1 đơn vị (do sợ). Nếu một con bò có sản lượng <= 0 thì không thể vắt được. Ta cần chọn một dãy con bò để vắt sao cho tổng sản lượng thu được là lớn nhất.

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

Cách Mô phỏng theo thứ tự ưu tiên (Giải pháp tham lam)

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

int main() {
    int n;
    cin >> n;
    int a[n];
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1, greater<>());
    int s = 0;
    for(int i = 1; i <= n; i++) {
        if(a[i] > 0) {
            s += a[i];
            for(int j = i + 1; j <= n; j++) {
                a[j] -= 1;
            }
        }
    }
    cout << s;
    return 0;
}

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

Cách tiếp cận này mô phỏng trực tiếp quá trình vắt sữa. Đầu tiên, ta sắp xếp các con bò theo sản lượng giảm dần. Sau đó, ta duyệt qua danh sách bò. Với mỗi con bò có sản lượng dương, ta cộng sản lượng đó vào tổng, và giảm sản lượng của tất cả các con bò còn lại (chưa được duyệt) đi 1. Điều này đảm bảo ta luôn ưu tiên vắt con bò có sản lượng lớn nhất tại thời điểm đó. Tuy nhiên, cách này không tối ưu về thời gian do có vòng lặp lồng nhau để giảm sản lượng.

Cách Công thức toán học (Giải pháp tối ưu)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;

    sort(a.begin(), a.end(), greater<long long>());

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long milk = a[i] - i;
        if (milk > 0) ans += milk;
        else break;
    }

    cout << ans;
    return 0;
}

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

Đây là giải pháp tối ưu. Ta nhận thấy rằng nếu ta chọn một dãy con bò để vắt, thì con bò nào được vắt ở vị trí thứ k (tính từ 1) sẽ bị giảm sản lượng đi (k-1) đơn vị do các bước vắt trước đó. Để tối đa hóa tổng sản lượng, ta nên chọn các con bò có sản lượng ban đầu lớn nhất và vắt chúng theo thứ tự giảm dần. Nếu ta sắp xếp mảng a giảm dần, con bò thứ i (tính từ 0) sẽ được vắt ở bước thứ i+1, do đó sản lượng thực thu được là a[i] - i. Chỉ khi a[i] - i > 0 thì việc vắt con bò này mới có lãi. Ta chỉ cần cộng các giá trị dương này lại.

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

Bài học kinh nghiệm

• Thứ tự vắt sữa tối ưu luôn là vắt các con bò có sản lượng ban đầu lớn trước (vì chúng chịu phạt giảm sản lượng tốt hơn).
• Giảm sản lượng của các con bò còn lại sau mỗi bước vắt tương đương với việc giảm chỉ số 'thời gian' của các con bò đó.
• Nếu con bò có chỉ số a[i] <= số thứ tự của nó trong thứ tự vắt (tính từ 0), thì không nên vắt nó vì sản lượng nhận về sẽ <= 0.

Lỗi thường gặp

• Quên sắp xếp lại mảng sau mỗi lần vắt (nếu mô phỏng không đúng logic tham lam).
• Sử dụng biến có kiểu dữ liệu quá nhỏ (ví dụ: int) dẫn đến tràn số nếu tổng sản lượng lớn.
• Lầm tưởng rằng thứ tự vắt phải phụ thuộc vào thứ tự xuất hiện của bò trong input, trong khi thực tế ta có thể chọn bất kỳ thứ tự nào.