Chương trình C++ đếm tối thiểu phép toán để tổng tiền tố đổi dấu luân phiên

Cho mảng A kích thước N. Mỗi phép: chọn phần tử +/- 1. Yêu cầu: (1) mọi tổng tiền tố ≠ 0. (2) dấu tổng tiền tố liên tiếp khác nhau. Tìm số phép tối thiểu.

Ví dụ

Với A=[1,-3,1,0], đầu ra 4. Biến thành [1,-2,2,-2], tổng tiền tố: 1, -1, 1, -1.

Giải thuật

Thử 2 trường hợp: tổng tiền tố đầu tiên dương hoặc âm. Duyệt mảng, giữ tổng hiện tại sum. Nếu tổng tiếp theo nsum vi phạm điều kiện (cùng dấu hoặc bằng 0), điều chỉnh phần tử hiện tại đủ lớn để nsum có dấu ngược và ≠ 0. Cộng số phép điều chỉnh. Lấy min 2 trường hợp.

Mã C++

#include <bits/stdc++.h>
using namespace std;

int util(vector<int> A, int s) {
    int n = A.size();
    int ret = 0, 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 / Đầu ra

Input: { 1, -3, 1, 0 }
Output: 4