Lật về 0 trong C++

Cho mảng nums chỉ chứa 0 và 1. Một phép toán: chọn chỉ số i, lật nums[i] và tất cả phần tử bên phải. Tìm số phép toán tối thiểu để biến toàn bộ mảng thành 0.

Ví dụ: [1,0,1] → 3 (lật i=0 → [0,1,0], i=1 → [0,0,1], i=2 → [0,0,0]).

Giải thuật: Dùng mảng op lưu số lần lật ảnh hưởng đến mỗi vị trí. Duyệt trái sang phải, nếu (nums[i] + op[i]) % 2 == 1 thì phải lật tại i.

Ví dụ

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

class Solution {
public:
    int solve(vector<int>& nums) {
        int n = nums.size();
        vector<int> op(n);
        int ret = 0;
        for (int i = 0; i < n; i++) {
            if (i - 1 >= 0) op[i] += op[i-1];
            if ((nums[i] + op[i]) & 1) {
                op[i]++;
                ret++;
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,0,1};
    cout << (ob.solve(v));
}

Đầu vào

{1,0,1}

Đầu ra

3