与えられた条件に必要な操作の数を少なくともカウントするC++プログラム

N個の要素を持つ配列Aがあるとします。各操作で、要素を選択し、それを1ずつ増減します。少なくとも次の条件を満たすために必要な操作の数を見つける必要があります-

• 1からnの範囲のすべてのiについて、第1項から第i項までの項の合計は0ではありません

• 1からn-1の範囲のすべてのiについて、第1項から第i項までの項の符号は、第1項から（i + 1）項までの項の合計の符号とは異なります。

したがって、入力がA =[1、-3、1、0]の場合、出力は4になります。これは、4つの操作で1、-2、2、-2のようなシーケンスを変換できるためです。最初の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 }

出力

4