생성된 문자열 T의 가능한 최소 불균형을 찾는 C++ 프로그램

가능한 문자 '0', '1' 또는 '?'가 있는 문자열 S가 있다고 가정합니다. '?'가 나타날 때마다 교체하여 문자열 T를 만들고 싶습니다. 0 또는 1로. T의 불균형은 다음과 같습니다. S의 l번째와 r번째 문자 사이에서 0과 1의 발생 횟수 사이의 모든 절대 차이의 최대값, 여기서 0 <=l <=r

따라서 입력이 S ="0??0"과 같으면 출력은 2

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

Define a function check(), this will take S, x,
L := 0, R = x
B := true
for initialize i := 0, when i < size of S, update (increase i by 1), do:
   if S[i] is same as '0', then:
      decrease L and R by 1, each
   if S[i] is same as '1', then:
      increase L and R by 1, each
   if S[i] is same as '?', then:
      if L is same as R, then:
         B := false
         (decrease L by 1)
         (increase R by 1)
   if R is same as x + 1, then:
      if B is non-zero, then:
         (decrease R by 1)
      Otherwise
         R := R - 2
   if L < 0, then:
      if B is non-zero, then:
         (increase L by 1)
      Otherwise
         L := L + 2
   if L > R, then:
      return false
return true
From the main method, do the following
L := 1, R := 1000000
while L <= R, do:
   Mid := floor of (L + R)/2
      if check(S, Mid), then:
         R := Mid - 1
      Otherwise
         L := Mid + 1
return R + 1

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
bool check(string S, int x) {
   int L = 0, R = x;
   bool B = true;
   for (int i = 0; i < S.size(); i++) {
      if (S[i] == '0')
         L--, R--;
      if (S[i] == '1')
         L++, R++;
      if (S[i] == '?') {
         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;
}

입력

0??0

출력

2