Số lần lật bit K liên tiếp tối thiểu trong C++

Cho mảng A chỉ chứa 0 và 1. Một phép lật K-bit chọn một mảng con liên tiếp độ dài K và đảo ngược tất cả các bit. Tìm số phép lật tối thiểu để không còn 0 nào. Nếu không thể, trả về -1.

Ví dụ: A=[0,0,0,1,0,1,1,0], K=3 → 3 phép lật.

Giải thuật

1. Sử dụng mảng moves[] lưu số lần lật bắt đầu tại mỗi vị trí (kỹ thuật difference array).
2. Duyệt i từ 0 đến n-K:
   • Tích lũy moves[i] += moves[i-1] (nếu i>0).
   • Giá trị thực tế tại i sau các phép lật: (moves[i]%2 + A[i])%2. Nếu bằng 0 (tức là bit 0), cần lật tại i.
   • Tăng moves[i], giảm moves[i+K] (nếu i+K < n), tăng counter.
3. Kiểm tra các vị trí còn lại (i từ n-K+1 đến n-1): nếu sau khi tích lũy moves mà bit vẫn là 0 → trả về -1.
4. Trả về counter.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int minKBitFlips(vector<int>& A, int K){
        int n = A.size();
        vector<int> moves(n);
        int counter = 0;
        for (int i = 0; i + K <= n; i++) {
            if (i > 0) moves[i] += moves[i-1];
            if (!(((moves[i] % 2) + A[i]) % 2)) {
                moves[i] += 1;
                if (i + K < n) moves[i + K] -= 1;
                counter++;
            }
        }
        for (int i = n - K + 1; i < n; i++) {
            if (i > 0) moves[i] += moves[i-1];
            if (!(((moves[i] % 2) + A[i]) % 2)) return -1;
        }
        return counter;
    }
};
int main(){
    Solution ob;
    vector<int> v = {0,0,0,1,0,1,1,0};
    cout << (ob.minKBitFlips(v, 3));
}

Đầu vào

{0,0,0,1,0,1,1,0}, 3

Đầu ra

3