Chương trình C++ tìm độ lệch tối thiểu của chuỗi nhị phân sau khi thay '?'

Mô tả bài toán

Chuỗi S gồm '0','1','?'. Thay mỗi '?' bằng 0 hoặc 1 tạo chuỗi T. Độ lệch (unbalancedness) = max độ chênh lệch tuyệt đối giữa số 0 và 1 trên mọi đoạn con. Tìm độ lệch nhỏ nhất có thể.

Ví dụ

S="0??0". Đầu ra: 2.

Thuật toán (Binary Search + Kiểm tra khả thi)

1. Binary search kết quả x từ 1 đến 1e6.
2. Hàm check(S,x): duyệt chuỗi, giữ khoảng [L,R] của chênh lệch (số 1 - số 0) có thể đạt được.
3. Ký tự '0': L--,R--; '1': L++,R++; '?': mở rộng L--,R++.
4. Giới hạn L≥0, R≤x (điều chỉnh nếu vượt). Nếu R → false.
5. Cuối chuỗi nếu hợp lệ → true.

Đoạn mã C++

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

bool check(string S,int x){
    int L=0,R=x;
    bool B=true;
    for(char ch:S){
        if(ch=='0') L--,R--;
        else if(ch=='1') L++,R++;
        else{
            if(L==R) B=false;
            L--; R++;
        }
        if(R==x+1){ if(B) R--; else R-=2; }
        if(L<0){ if(B) L++; else L+=2; }
        if(L>R) return false;
    }
    return true;
}

int solve(string S){
    int L=1,R=1e6;
    while(L<=R){
        int Mid=(L+R)>>1;
        if(check(S,Mid)) R=Mid-1;
        else L=Mid+1;
    }
    return R+1;
}

int main(){
    string S="0??0";
    cout << solve(S) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: 0??0

Output: 2