C ++中过马路所需的最小初始能量
假设我们有一个存储正负数的数组。该数组代表从街道的一端到另一端的检查点。正值和负值表示检查点的能量。正值可以增加能量，负数可以减少能量。我们必须找到过马路的初始能级，以使能级永远不会变为0或小于0。
假设我们有一个数组A={4，-6，2，3}。令初始能量为0。因此，在到达第一个检查点后，能量为4。现在，到第二个检查点，能量将为4+(-6)=-2。因此能量小于0。因此我们必须从3开始。因此，在第一个之后，它将是3+4=7，在第二个检查点之后，它将是7+(-6)=1。
算法
minInitEnergy(arr, n):
begin
initEnergy := 0
currEnergy := 0
flag := false
for i in range 0 to n, do
currEnergy := currEnergy + arr[i]
if currEnergy <= 0, then
initEnergy := initEnergy + absolute value of currEnergy + 1
currEnergy := 1
flag := true
end if
done
if flag is false, return 1, otherwise return initEnergy
end示例
#include <iostream>
#include <cmath>
using namespace std;
int minInitEnergy(int arr[], int n){
int initEnergy = 0;
int currEnergy = 0;
bool flag = false;
for (int i = 0; i<n; i++){
currEnergy = currEnergy + arr[i];
if (currEnergy <= 0){
initEnergy = initEnergy + abs(currEnergy) + 1;
currEnergy = 1;
flag = true;
}
}
if (flag == false)
return 1;
else
return initEnergy;
}
int main() {
int A[] = {4, -6, 2, 3};
int n = sizeof(A)/sizeof(A[0]);
cout << "Minimum Energy: " << minInitEnergy(A, n);
}输出结果
Minimum Energy: 3