Năng lượng ban đầu tối thiểu cần thiết để băng qua đường trong C ++

Giả sử chúng ta có một mảng chứa các số dương và số âm. Mảng này đại diện cho trạm kiểm soát từ đầu này đến đầu kia của các con phố. Các giá trị âm và dương đại diện cho năng lượng tại các điểm kiểm tra. Các giá trị dương có thể tăng năng lượng, và số âm làm giảm năng lượng. Chúng ta phải tìm mức năng lượng ban đầu để băng qua đường, sao cho mức năng lượng không bao giờ trở thành 0 hoặc nhỏ hơn 0.

Giả sử chúng ta có một mảng A ={4, -6, 2, 3}. Cho năng lượng ban đầu là 0. Vì vậy, sau khi đến điểm kiểm tra đầu tiên, năng lượng là 4. Bây giờ, để đi đến điểm kiểm tra thứ hai, năng lượng sẽ là 4 + (-6) =-2. Vì vậy, năng lượng nhỏ hơn 0. Vì vậy chúng ta phải bắt đầu hành trình với 3. Vì vậy, sau chặng đầu tiên sẽ là 3 + 4 =7, và sau khi đến trạm kiểm soát thứ hai, nó sẽ là 7 + (-6) =1.

Thuật toán

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

Ví dụ

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

Đầu ra

Minimum Energy: 3