Hiểu bài toán

Bài toán PRjchain liên quan đến việc tìm giá trị năng lượng ban đầu (E) nhỏ nhất sao cho có thể thực hiện thành công chuỗi các dự án. Với mỗi dự án i, ta cần một lượng năng lượng bắt đầu (a[i]) để thực hiện và sau khi hoàn thành sẽ thu được năng lượng (b[i]). Ta có thể thực hiện dự án i nếu năng lượng hiện tại >= a[i], và sau đó năng lượng sẽ thay đổi thành (năng lượng hiện tại - a[i] + b[i]).

Mục tiêu: Tìm số nguyên dương E nhỏ nhất sao cho sau khi thực hiện tất cả n dự án theo một thứ tự nhất định, năng lượng cuối cùng >= 0.

Điều kiện: Ta có thể sắp xếp lại thứ tự các dự án một cách tự do.

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

Cách Sắp xếp đơn giản (Heuristic)

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

#define int long long
const int mxn = 100000 + 7;

int n;
pair<int,int> a[mxn];

// Hàm sắp xếp theo quy tắc của bạn
bool cmp(pair<int,int> A, pair<int,int> B){
    int x = A.first - A.second;
    int y = B.first - B.second;

    if(x <= 0 && y >= 0) return true;      // Lãi trước, Lỗ sau
    if(x >= 0 && y <= 0) return false;     // Đảm bảo Lãi trước, Lỗ sau
    if(x <= 0 && y <= 0) return A.first < B.first; // Cả 2 đều lỗ: cái nào cần ít vốn hơn trước
    if(x >= 0 && y >= 0) return A.second > B.second; // Cả 2 đều lãi: cái nào lãi nhiều hơn trước
    return true;
}

bool check(int x){
    for(int i = 1; i <= n; i++){
        if(x < a[i].first) return false;
        x = x - a[i].first + a[i].second;
    }
    return x >= 0;
}

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i].first;
    for(int i = 1; i <= n; i++) cin >> a[i].second;

    sort(a + 1, a + n + 1, cmp);

    // Binary Search for minimum E
    int l = 0, r = 2e18; // bound足够大
    int ans = 0;
    while(l <= r){
        int mid = l + (r - l) / 2;
        if(check(mid)){
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans;
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    // freopen("prjchain.inp", "r", stdin);
    // freopen("prjchain.out", "w", stdout);
    solve();
}

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

Đây là cách tiếp cận được sử dụng trong các solution mẫu. Nó bao gồm hai phần:

1. Sắp xếp: Các dự án được chia làm 4 loại dựa vào hiệu số a[i] - b[i] (lãi hay lỗ) và b[i] - a[i] (lãi hay lỗ). Logic sắp xếp ưu tiên:
   • Dự án lãi (a[i] < b[i]) luôn đi trước dự án lỗ (a[i] > b[i]).
   • Trong nhóm dự án lãi, ưu tiên dự án có b[i] lớn hơn.
   • Trong nhóm dự án lỗ, ưu tiên dự án có a[i] nhỏ hơn.
   • Logic này là một heuristic để giảm thiểu năng lượng đầu vào cần thiết.
2. Tìm kiếm nhị phân (Binary Search): Vì giá trị năng lượng đầu vào E có mối quan hệ đơn điệu (nếu E đủ thì E+1 cũng đủ), ta có thể dùng binary search để tìm giá trị nhỏ nhất. Hàm check(E) giả lập việc thực hiện chuỗi dự án đã sắp xếp để kiểm tra tính hợp lệ.

Cách Tính toán trực tiếp (Tối ưu)

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

long long n;
vector<pair<long long,long long> > a;
vector<pair<long long,long long> > lai, lo;
vector<pair<long long,long long> > a1;

bool kt(pair<long long,long long> x,pair<long long,long long> y) {
    return x.second>y.second;
}
int main()
{
    freopen("prjchain.inp","r",stdin);
    freopen("prjchain.out","w",stdout);
    cin >> n;
    a.resize(n);
    for (long long i=0;i<n;i++) cin >> a[i].first;
    for (long long i=0;i<n;i++) cin >> a[i].second;
    for (long long i=0;i<n;i++) {
        if (a[i].second-a[i].first >= 0) lai.push_back(a[i]); // Lãi hoặc hòa vốn
        else lo.push_back(a[i]); // Lỗ
    }
    sort(lai.begin(),lai.end()); // Tang dan theo a (chi phi)
    sort(lo.begin(),lo.end(),kt); // Giam dan theo b (thu nhap)
    a1.insert(a1.end(),lai.begin(),lai.end());
    a1.insert(a1.end(),lo.begin(),lo.end());

    long long vonht=0, von=0;
    for (int t=0;t<n;t++) {
        if (vonht < a1[t].first) {
            von+=a1[t].first-vonht;
            vonht=a1[t].first;
        }
        vonht = vonht - a1[t].first + a1[t].second;
    }
    cout << von;
    return 0;
}

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

Phương pháp này loại bỏ bước Binary Search. Thay vào đó, nó tính toán trực tiếp giá trị năng lượng đầu vào tối thiểu sau khi đã sắp xếp xong.

Cụ thể:

1. Sắp xếp tương tự Approach 1 (tách riêng lãi và lỗ).
2. Duyệt qua chuỗi đã sắp xếp và theo dõi vonht (năng lượng hiện tại) và von (năng lượng đầu vào tổng cộng đã bỏ ra).
   • Nếu vonht hiện tại nhỏ hơn a[i] cần thiết, ta phải nạp thêm năng lượng: von += (a[i] - vonht). Đồng thời vonht được set về a[i].
   • Sau đó thực hiện dự án: vonht = vonht - a[i] + b[i].

Công thức này tính chính xác lượng năng lượng bổ sung cần thiết để duy trì chuỗi dự án.

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

Bài học kinh nghiệm

• Bài toán có thể chia thành 2 loại chính: Dự án sinh lời (a < b) và dự án mất vốn (a > b). Luôn thực hiện các dự án sinh lời trước.
• Trong nhóm dự án sinh lời, nên ưu tiên项目 có chi phí a thấp hơn (hoặc b cao hơn) để giảm thiểu vốn ban đầu.
• Trong nhóm dự án mất vốn, nên ưu tiên项目 có thu nhập b cao hơn (hoặc a thấp hơn) để tích lũy nhiều năng lượng trước khi đối mặt với dự án tiếp theo.

Lỗi thường gặp

• Sử dụng int thay vì long long dẫn đến tràn số do tổng năng lượng có thể rất lớn.
• Sai lệch trong hàm so sánh (sort comparator) có thể dẫn đến thứ tự sai và kết quả không tối ưu.
• Quên kiểm tra năng lượng âm cuối cùng (x >= 0).