주어진 조건에 필요한 연산 수를 계산하는 C++ 프로그램

<시간/>

N개의 요소가 있는 배열 A가 있다고 가정합니다. 각 작업에서 요소를 선택하고 1씩 늘리거나 줄입니다. 다음 조건을 충족하는 데 필요한 작업의 수는 최소한 찾아야 합니다. -

범위 1에서 n까지의 모든 i에 대해 첫 번째부터 i번째 항까지의 항의 합은 0이 아닙니다.
범위 1에서 n - 1에 있는 모든 i에 대해 1번째부터 i번째 항까지의 항의 부호는 1번째부터 (i+1)번째 항까지의 항의 합계의 부호와 다릅니다.

따라서 입력이 A =[1, -3, 1, 0]과 같으면 출력은 4가 됩니다. 왜냐하면 1, -2, 2, -2와 같은 시퀀스를 4개의 연산으로 변환할 수 있기 때문입니다. 첫 번째 1, 2, 3, 4항의 합은 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 }