โปรแกรม C++ นับจำนวนการดำเนินการที่จำเป็นสำหรับเงื่อนไขที่กำหนดเป็นอย่างน้อย

สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ N ในแต่ละการดำเนินการ เราเลือกองค์ประกอบหนึ่งและเพิ่มหรือลด 1 รายการ เราต้องหาอย่างน้อยจำนวนการดำเนินการที่จำเป็นเพื่อให้เป็นไปตามเงื่อนไขต่อไปนี้ -

• สำหรับทุก ๆ i ในช่วง 1 ถึง n ผลรวมของเทอมที่ 1 ถึงเทอมที่ 1 ไม่ใช่ 0

• สำหรับทุกๆ i ในช่วง 1 ถึง n - 1 เครื่องหมายของเทอมที่ 1 ถึงเทอมที่ 1 จะแตกต่างจากเครื่องหมายของผลรวมของเทอมจากเทอมที่ 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 }

ผลลัพธ์

4