最初の山で最大の干し草の俵を数えるC++コード

n個の要素と別の値dを持つ配列Aがあるとします。農民は会社にn個の干し草を配置しました。 i番目の山にはA[i]干し草の俵が含まれています。毎日、牛は任意の山の干し草ベールを隣接する山に移動することを選択できます。牛は、それ以外の場合は何もしない日にこれを行うことができます。牛は、d日で最初の山の干し草の俵を最大化したいと考えています。最初の山の干し草の俵の最大数を数える必要があります。

したがって、入力がd=5のような場合。 A =[1、0、3、2]の場合、出力は3になります。これは、最初の日は3日から2日に移動し、2日目には再び3日から2日に移動し、次の2日は2日から1日を通過するためです。

ステップ

これを解決するには、次の手順に従います-

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