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