สมมติว่าเรามีสตริง S ที่มีอักขระที่เป็นไปได้ '0', '1' หรือ '?' เราต้องการสร้างสตริง T โดยแทนที่ '?' แต่ละรายการ ด้วย 0 หรือ 1 ความไม่สมดุลของ T เป็นดังนี้:สูงสุดของผลต่างสัมบูรณ์ทั้งหมดระหว่างจำนวนการเกิดขึ้นของ 0 และ 1 ระหว่างอักขระ lth และ rth ใน S โดยที่ 0 <=l <=r <ขนาดของ S เราต้อง หาค่าความไม่สมดุลของ T.
ดังนั้น หากอินพุตเป็น 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
