मान लीजिए S एक स्ट्रिंग है जिसमें संभावित वर्ण '0', '1' या '?' हैं। हम '?' के प्रत्येक घटना को 0 या 1 से बदलकर स्ट्रिंग T बनाना चाहते हैं। T का अनबैलेंस्डनेस इस प्रकार है: S में l-वें और r-वें वर्ण के बीच 0 और 1 की घटनाओं की संख्या के निरपेक्ष अंतर का अधिकतम मान, जहाँ 0 <= l <= r < S का आकार। हमें T के न्यूनतम संभावित अनबैलेंस्डनेस की गणना करनी है।
उदाहरण के लिए, यदि इनपुट है S = "0??0", तो आउटपुट 2 होगा।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
एक फंक्शन check() परिभाषित करें जो S, x लेता है:
L := 0, R = x
B := true
i := 0 से S के आकार-1 तक:
यदि S[i] == '0', तो:
L और R प्रत्येक को 1 घटाएँ
यदि S[i] == '1', तो:
L और R प्रत्येक को 1 बढ़ाएँ
यदि S[i] == '?', तो:
यदि L == R, तो B := false
L घटाएँ, R बढ़ाएँ
यदि R == x + 1, तो:
यदि B सत्य है, तो R घटाएँ
अन्यथा R := R - 2
यदि L < 0, तो:
यदि B सत्य है, तो L बढ़ाएँ
अन्यथा L := L + 2
यदि L > R, तो false लौटाएँ
true लौटाएँ
मुख्य विधि से:
L := 1, R := 1000000
जब तक L <= R:
Mid := floor((L + R)/2)
यदि check(S, Mid), तो R := Mid - 1
अन्यथा L := Mid + 1
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