โปรแกรม C++ หาค่า Unbalancedness ต่ำสุดของสตริงไบนารี

สตริง S ประกอบด้วย 0, 1, ? สร้าง T โดยแทน ? ด้วย 0 หรือ 1 "Unbalancedness" = ค่าสูงสุดของ |count(0) - count(1)| ในทุก substring ของ T หาค่า Unbalancedness ต่ำสุดที่เป็นไปได้

ตัวอย่าง: S="0??0" ผลลัพธ์: 2

ขั้นตอนการแก้ปัญหา (Binary Search + Greedy Check)

1. Binary Search คำตอบ x ในช่วง [1, 1e6]
2. ฟังก์ชัน check(S, x): จำลองการแทน ? โดยรักษาให้ความต่างระหว่าง 0 และ 1 อยู่ในช่วง [-x, x] ตลอด
   • ตัวแปร L, R = ช่วงความต่างที่เป็นไปได้ (เริ่ม 0, x)
   • ตัวแปร B = ยังมีความยืดหยุ่นหรือไม่
   • อ่าน S ทีละตัว: 0 → L--,R--; 1 → L++,R++; ? → L--,R++ (ถ้า L==R ตั้ง B=false)
   • Clamp L,R ให้อยู่ใน [0, x] โดยคำนึงถึง B
   • ถ้า L > R → false
3. คืน R+1 จาก Binary Search

ตัวอย่างโค้ด 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 = 1000000;
    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;
}

อินพุต / เอาต์พุต

Input: 0??0

Output: 2