Tối đa hóa số gạch khô trên đống đầu tiên trong d ngày bằng C++

Mô tả bài toán

Cho mảng A n đống gạch khô, A[i] số gạch. Mỗi ngày bò có thể chuyển 1 gạch từ đống i sang đống liền kề (i-1 hoặc i+1). Trong d ngày, tối đa hóa số gạch trên đống 0.

Ví dụ

d=5, A=[1,0,3,2] → Output: 3. (Chuyển từ đống 2→1 hai ngày, rồi 1→0 hai ngày).

Thuật toán

Xử lý từ đống 1 đến n-1: từ đống i, tối đa có thể chuyển min(A[i], d/i) gạch về đống 0 (vì mỗi gạch cần i ngày). Cập nhật d và kết quả.

Code C++

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

int solve(int d, vector A) {
    int a0 = A[0];
    int n = A.size();
    for (int i = 1; i < n; i++) {
        int w = min(A[i], d / i);
        a0 += w;
        d -= w * i;
    }
    return a0;
}

int main() {
    int d = 5;
    vector A = {1,0,3,2};
    cout << solve(d, A) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: 5, {1,0,3,2}

Output: 3