C++ प्रोग्राम दी गई शर्तों के लिए कम से कम कितने ऑपरेशनों की आवश्यकता है, यह गिनने के लिए

मान लीजिए कि हमारे पास एन तत्वों के साथ एक सरणी ए है। प्रत्येक ऑपरेशन में, हम एक तत्व चुनते हैं और इसे 1 से बढ़ाते या घटाते हैं। हमें कम से कम यह पता लगाना होगा कि निम्नलिखित शर्तों को पूरा करने के लिए कितने ऑपरेशन की आवश्यकता है -

1 से n तक के प्रत्येक i के लिए, 1 से ith पद तक के पदों का योग 0 नहीं है
1 से n - 1 तक के प्रत्येक i के लिए, 1 से ith पद तक के पदों का चिह्न 1 से (i+1)वें पद तक के पदों के योग के चिह्न से भिन्न होता है।

इसलिए, यदि इनपुट ए =[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 }