C++ 代码，用于计算第一个堆叠上干草堆的最大值

假设我们有一个包含 n 个元素的数组 A 和另一个值 d。一个农民在农场上排列了 n 个干草堆。第 i 个堆叠包含 A[i] 个干草堆。每天，奶牛可以选择将任何堆叠中的一个干草堆移至相邻的堆叠。奶牛可以这样做，也可以什么都不做。奶牛希望在 d 天内将第一个堆叠中的干草堆数量最大化。我们必须计算第一个堆叠上的干草堆的最大数量。

因此，如果输入为 d = 5; A = [1, 0, 3, 2]，则输出将为 3，因为在第一天从第 3 个移动到第 2 个，在第二天再从第 3 个移动到第 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

Arnab Chakraborty

更新于: 15-03-2022

114 次浏览

开启 职业生涯

完成课程并获得认证

开始