โปรแกรม C++ นับการดำเนินการน้อยที่สุดทำให้ผลรวมย่อยสลับเครื่องหมาย

คำอธิบายปัญหา

สมมติว่าเรามีอาร์เรย์ A N องค์ประกอบ ใน 1 ครั้ง เลือกองค์ประกอบและบวกหรือลบ 1 ต้องการหาขั้นตอนน้อยที่สุดทำให้:

• สำหรับทุก i 1 ถึง n ผลรวมพจน์ที่ 1 ถึง i ไม่เป็น 0
• สำหรับทุก i 1 ถึง n-1 เครื่องหมายของผลรวม 1 ถึง i ต่างจากเครื่องหมายผลรวม 1 ถึง i+1

ขั้นตอนการแก้ปัญหา

n := ขนาดของ A
ret := 0
sum := 0
สำหรับ ai ใน A:
    nsum := sum + ai
    ถ้า s > 0:
        ถ้า nsum <= 0:
            ret := ret + |nsum| + 1
            ai := ai + |nsum| + 1
    มิฉะนั้น:
        ถ้า nsum >= 0:
            ret := ret + nsum + 1
            ai := ai - (nsum + 1)
    sum := sum + ai
    s := s * -1
คืนค่า ret

ตัวอย่างโค้ด C++

#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