พลังงานเริ่มต้นขั้นต่ำที่จำเป็นในการข้ามถนนใน 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