প্রদত্ত অবস্থার জন্য কমপক্ষে কতগুলি অপারেশন প্রয়োজন তা গণনা করতে C++ প্রোগ্রাম

ধরুন আমাদের কাছে N উপাদান সহ একটি অ্যারে রয়েছে। প্রতিটি ক্রিয়াকলাপে, আমরা একটি উপাদান বাছাই এবং এটিকে 1 দ্বারা বৃদ্ধি বা হ্রাস করি। নিম্নলিখিত শর্তগুলি পূরণ করার জন্য আমাদের কমপক্ষে কতগুলি অপারেশন প্রয়োজন তা খুঁজে বের করতে হবে -

1 থেকে n রেঞ্জের প্রতিটি i এর জন্য, 1ম থেকে ith টার্ম পর্যন্ত পদের যোগফল 0 নয়
1 থেকে n - 1 পরিসরের প্রতিটি i-এর জন্য, 1ম থেকে ith পদের পদের চিহ্নটি 1ম থেকে (i+1)তম পদের পদের যোগফলের চিহ্ন থেকে আলাদা৷

সুতরাং, যদি ইনপুটটি A =[1, -3, 1, 0] এর মতো হয়, তবে আউটপুট হবে 4, কারণ আমরা 1, -2, 2, -2 এর মতো ক্রমটিকে চারটি অপারেশন দ্বারা রূপান্তর করতে পারি। প্রথম এক, দুই, তিন এবং চারটি পদের যোগফল হল 1, -1, 1 এবং -1৷

পদক্ষেপ

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n := size of A
ret := 0
sum := 0
for each ai in A, do
   nsum := sum + ai
   if s > 0, then:
      if nsum <= 0, then:
         ret := ret + |nsum|
         ai := ai + |nsum|
      Otherwise
         if nsum >= 0, then:
            ret := ret + nsum + 1
            ai := ai - (nsum + 1)
      sum := sum + ai
      s := s * -1
return ret

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;

int util(vector<int> A, int s){
   int n = A.size();
   int ret = 0;
   int sum = 0;
   for (int ai : A){
      int nsum = sum + ai;
      if (s > 0){
         if (nsum <= 0){
            ret += abs(nsum) + 1;
            ai = ai + abs(nsum) + 1;
         }
      } else{
         if (nsum >= 0){
            ret += nsum + 1;
            ai = ai - (nsum + 1);
         }
      }
      sum += ai;
      s *= -1;
   }
   return ret;
}
int solve(vector<int> A){
   int res = min(util(A, 1), util(A, -1));
   return res;
}
int main(){
   vector<int> A = { 1, -3, 1, 0 };
   cout << solve(A) << endl;
}

ইনপুট

{ 1, -3, 1, 0 }