Nếu như theo ý mình hiểu thì do tổng số hàng hai kho vừa đủ để cung cấp cho $N$ công trình nên ta sẽ cần vận chuyển đúng $R$ đơn vị hàng từ kho A và đúng $(\sum D_i) - R$ đơn vị hàng từ kho $B$ đến $N$ công trình

Ý tưởng

Nếu đúng như ý mình hiểu thì ta sẽ sử dụng thuật toán tham lam cho bài này.

Giả sử ta không có kho hàng A, khi đó ta cần vận chuyển đúng $\sum D_i$ đơn vị hàng từ kho B tới các công trình. Chi phí lúc này của ta sẽ là $c = \sum_{i=1}^{N} (B_i \times D_i)$

Tất nhiên chi phí $c$ không phải đáp án cần tìm của chúng ta, vì ta cần chuyển $R$ đơn vị hàng từ nhiệm vụ của B sang cho của A. Nếu ta chuyển 1 đơn vị hàng có đích đến là công trình thứ $i$ từ kho hàng B sang kho hàng A, chi phí mới của chúng ta sẽ là $c' = c - B_i + A_i$

Do đó, để tối ưu chi phí, ta sẽ chuyển 1 đơn vị hàng giao tới công trình $i$ từ nhiệm vụ của B sang cho nhiệm vụ của A khi:

- $A_i - B_i$ đạt giá trị nhỏ nhất.

- Kho hàng A đang có nhiệm vụ giao tới công trình $i$ số đơn vị hàng $x_i < D_i$.

Để tìm nhanh kho hàng $i$ thỏa mãn, ta có thể tạo một mảng $F$ gồm $N$ phần tử với định nghĩa $F_i = A_i - B_i$, sau đó sắp xếp danh sách lại.

Code (C++)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;

int n, r, d[maxn], a[maxn], b[maxn], ptr;
pair<int,int> diff[maxn];
long long ans; // tranh tran so

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // Nhap xuat file (neu co)
    if(fopen("transport.inp", "r")){
        freopen("transport.inp","r",stdin);
        freopen("transport.out","w",stdout);
    }
    // Nhap du lieu
    cin >> n >> r;
    for(int i=1;i<=n;i++) cin >> d[i];
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) {
        cin >> b[i];
        ans += b[i] * d[i];
        diff[i] = make_pair(a[i] - b[i], i);
        // Dung pair -> de truy vet
    }
    sort(diff+1,diff+n+1);
    ptr = 1;
    while(r > 0){
        if(d[diff[ptr].second] <= r){
            ans += (diff[ptr].first) * d[diff[ptr].second];
            r -= d[diff[ptr].second];
        }else{
            ans += (diff[ptr].first) * r;
            r = 0;
        }
        ptr++;
    }
    cout << ans;
    return 0;
}