Chương trình C ++ để đếm ít nhất bao nhiêu hoạt động cần thiết cho các điều kiện nhất định

Giả sử chúng ta có một mảng A với N phần tử. Trong mỗi phép toán, chúng ta chọn một phần tử và tăng hoặc giảm nó đi 1. Chúng ta phải tìm ít nhất bao nhiêu phép toán để thỏa mãn các điều kiện sau -

• Với mọi i trong phạm vi từ 1 đến n, tổng các số hạng từ số hạng thứ nhất đến số hạng thứ i không bằng 0

• Với mọi i trong phạm vi từ 1 đến n - 1, dấu của các số hạng từ số hạng thứ 1 đến thứ i khác với dấu của tổng các số hạng từ số hạng thứ 1 đến (thứ i + 1).

Vì vậy, nếu đầu vào là A =[1, -3, 1, 0], thì đầu ra sẽ là 4, bởi vì chúng ta có thể biến đổi chuỗi như 1, -2, 2, -2 bằng bốn phép toán. Tổng của một, hai, ba và bốn số hạng đầu tiên là 1, -1, 1 và -1.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

{ 1, -3, 1, 0 }

Đầu ra

4