Mã C ++ để đếm các kiện cỏ khô tối đa trên đống đầu tiên

Giả sử chúng ta có một mảng A với n phần tử và một giá trị khác d. Một nông dân đã sắp xếp n đống cỏ khô trên công ty. Cọc thứ i chứa A [i] kiện hay. Mỗi ngày, một con bò có thể chọn di chuyển các gói cỏ khô trong đống bất kỳ sang một đống liền kề. Con bò có thể làm điều này vào một ngày, nếu không thì không phải làm gì. Con bò muốn tối đa hóa các kiện cỏ khô trong đống đầu tiên trong d ngày. Chúng tôi phải đếm số lượng tối đa các kiện cỏ khô trên đống đầu tiên.

Vì vậy, nếu đầu vào giống như d =5; A =[1, 0, 3, 2], thì kết quả đầu ra sẽ là 3, bởi vì trong ngày đầu tiên chuyển từ thứ 3 sang thứ 2, vào ngày thứ hai lại chuyển từ thứ 3 sang thứ hai, sau đó vào hai ngày tiếp theo, chuyển thứ 2 sang thứ nhất.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

a0 := A[0]
n := size of A
for initialize i := 1, when i < n, update (increase i by 1), do:
   ai := A[i]
   w := minimum of ai and d / i
   a0 := a0 + w
   d := d - w * i
return a0

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
int solve(int d, vector<int> A){
   int a0 = A[0];
   int n = A.size();
   for (int i = 1; i < n; i++){
      int ai = A[i];
      int w = min(ai, d / i);
      a0 += w;
      d -= w * i;
   }
   return a0;
}
int main(){
   int d = 5;
   vector<int> A = { 1, 0, 3, 2 };
   cout << solve(d, A) << endl;
}

Đầu vào

5, { 1, 0, 3, 2 }

Đầu ra

3