첫 번째 더미에서 최대 건초 더미를 계산하는 C++ 코드

n개의 요소와 다른 값 d가 있는 배열 A가 있다고 가정합니다. 한 농부가 회사에 n개의 건초 더미를 배치했습니다. i번째 더미에는 A[i] 건초 더미가 있습니다. 매일 소는 아무 더미에 있는 건초 더미 하나를 인접한 더미로 옮길 수 있습니다. 소는 하루에 이것을 할 수 있고 그렇지 않으면 아무 것도 하지 않습니다. 소는 d일에 첫 번째 더미의 건초 더미를 최대화하려고 합니다. 첫 번째 더미에 있는 건초 더미의 최대 개수를 계산해야 합니다.

따라서 입력이 d =5와 같으면; A =[1, 0, 3, 2]인 경우 첫 번째 날에 3일에서 2일로 이동하고 두 번째 날에 다시 3일에서 두 번째로 이동한 다음 다음 이틀에 2일을 첫 번째로 전달하기 때문에 출력은 3이 됩니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

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

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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;
}

입력

5, { 1, 0, 3, 2 }

출력

3