Hiểu bài toán

Bài toán yêu cầu tìm số thùng hàng tối thiểu cần dùng để trả công cho việc chuyển tất cả hàng hóa từ N kho về một kho duy nhất. Với mỗi lần chuyển một thùng hàng từ kho A sang kho B, ta cần trả công một thùng hàng (tức là 'bốc' hàng đó). Mục tiêu là tìm cách chuyển hàng sao cho tổng số thùng hàng dùng để trả công là nhỏ nhất. Quan trọng là các thùng hàng này có thể dùng làm 'phí' chuyển các thùng hàng khác, tạo thành một quy trình tích lũy.

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

Cách Mô phỏng tham lam bằng hai con trỏ

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second


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

    int n; cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    sort(all(a));
    int dem = 0;
    int l = 0, r = n - 1;
    while (l < r){
        if (a[l] != 0){
            r--;
            dem++;
            a[l]--;
        }
        else l++;
    }
    cout << dem;

    return 0;
}

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

Hướng tiếp cận này mô phỏng trực tiếp quá trình chuyển hàng. Ta sắp xếp mảng số thùng hàng tăng dần. Sử dụng hai chỉ số l (kho có ít hàng nhất) và r (kho có nhiều hàng nhất).

• Trong khi l < r: Nếu kho l còn hàng (a[l] > 0), ta dùng 1 thùng hàng từ kho l để chuyển 1 thùng hàng từ kho r về kho l (hoặc một kho trung gian, nhưng về tổng số thì ta giảm hàng ở l và giảm số lượng kho ở r). Cụ thể, a[l]-- và r-- (kho r đã được dọn sạch hoặc hợp nhất), dem++ (tăng số thùng trả công).
• Nếu a[l] == 0, ta loại bỏ kho này (l++). Vòng lặp kết thúc khi chỉ còn một kho, và dem chính là kết quả.

Cách Tối ưu hóa Logic (Giảm số lần truy cập)

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int a[100005];
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // Sắp xếp mảng a theo thứ tự tăng dần
    sort(a, a + n);

    int steps = 0;
    int idx = 0; // chỉ số kho hàng đầu tiên (ít nhất)
    while (n - idx > 1) {
        // Chuyển kho nhiều nhất vào kho ngay phía trước nó
        a[idx + 1] += a[n-1];
        a[idx]--; // bớt 1 thùng ở kho ít nhất
        steps++;
        // Nếu kho ít nhất đã hết hàng, tăng chỉ số
        while (idx < n && a[idx] == 0) {
            idx++;
        }
        // Giảm số kho còn lại (vì mỗi lần ghép là bỏ bớt 1 kho ở cuối)
        n--;
    }

    cout << steps << endl;

    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là phiên bản tối ưu hóa của phương pháp mô phỏng.

1. Sắp xếp mảng tăng dần.
2. Duyệt qua mảng, coi a[0] là kho chứa hàng dùng để bốc (kho trung tâm).
3. Vòng lặp while (n - idx > 1): Khi vẫn còn các kho khác ngoài kho trung tâm:
   • Cộng dồn hàng của kho lớn nhất (a[n-1]) vào kho trung tâm kế tiếp (a[idx+1]). Điều này mô phỏng việc dùng hàng từ kho trung tâm để trả công chuyển hàng.
   • Giảm 1 đơn vị hàng ở kho trung tâm hiện tại (a[idx]--) vì đã dùng 1 thùng để trả công.
   • Tăng số bước (steps).
   • Nếu kho trung tâm hiện tại hết hàng (a[idx] == 0), ta di chuyển chỉ số idx lên kho trung tâm mới.
   • Giảm n đi 1 (vì kho lớn nhất đã được xử lý). Cách này tránh việc giảm r từng bước một, thay vào đó 'nuốt chửng' cả kho lớn nhất ngay lập tức.

Cách Giải pháp dựa trên Tổng số hàng

#include <bits/stdc++.h>
#define fo(name) if (fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define fast_io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
#define fi first
#define se second
using namespace std;
typedef long long ll;
void solve(){
    ll n; cin>>n;
    vector<ll> a(n);
    for (auto &x:a) cin>>x;
    sort(all(a));
    ll d=0;
    ll s=0;
    vector<ll> f;
    for (auto &x:a){
        s+=x;
        f.pb(s);
    }
    for (ll i=n-2;i>=0;i--){
        d++;
        if (d>=f[i-1]) break;
    }
    cout<<d;
}
int main(){
    fast_io
    fo("name");
    ll t=1; //cin>>t;
    while (t--) solve();
    return 0;
}

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

Đây là một cách tiếp cận khác, có vẻ như dựa trên việc phân tích tổng số hàng.

• Sắp xếp mảng tăng dần.
• Tính mảng cộng dồn f của a (tổng số hàng tích lũy).
• Duyệt từ n-2 trở lui:
  • Tăng d (số thùng trả công).
  • Nếu d >= tổng số hàng của các kho trước đó (f[i-1]), dừng lại. Gợi ý của phương pháp này là số thùng trả công cần ít nhất phải đủ lớn để 'che phủ' tổng số hàng của các kho còn lại (trừ kho lớn nhất) để có thể chuyển chúng về.

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

Bài học kinh nghiệm

• Bài toán có thể coi là tìm cách tích lũy hàng hóa để trả công. Kho nào có nhiều hàng có thể dùng làm nguồn hàng để trả công cho việc chuyển hàng từ các kho khác về.
• Sắp xếp mảng là bước tiền xử lý quan trọng để áp dụng các chiến lược tham lam.

Lỗi thường gặp

• Không sắp xếp mảng trước khi xử lý, dẫn đến logic chuyển hàng không tối ưu.
• Sử dụng kiểu dữ liệu nhỏ (ví dụ int) cho các biến tính tổng hoặc số bước có thể gây tràn số nếu N lớn và a_i lớn (dù a_i <= 1000, nhưng tổng tích lũy qua nhiều bước có thể lớn).