Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

जनरेटेड स्ट्रिंग T के न्यूनतम संभावित अनबैलेंस्डनेस ज्ञात करने का C++ प्रोग्राम


मान लीजिए 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
  1. - C++ में स्ट्रिंग की लंबाई खोजने का प्रोग्राम

    एक स्ट्रिंग एक एक-आयामी कैरेक्टर सरणी है जो नल कैरेक्टर द्वारा समाप्त होती है। स्ट्रिंग की लंबाई नल कैरेक्टर से पहले स्ट्रिंग में कैरेक्टर्स की संख्या होती है। उदाहरण के लिए। char str[] = “The sky is blue”; उपरोक्त स्ट्रिंग में कैरेक्टर्स की संख्या = 15 स्ट्रिंग की लंबाई खोजने का एक प्रो

  1. - C++ प्रोग्राम: LCM (लघुत्तम समापवर्त्य) खोजें

    परिचयदो संख्याओं का लघुत्तम समापवर्त्य (LCM) वह सबसे छोटी संख्या है जो दोनों का गुणक है। उदाहरण के लिए: मान लें हमारे पास दो संख्याएं हैं: 15 और 9। 15 = 5 * 3 9 = 3 * 3 इसलिए, 15 और 9 का LCM 45 है। उदाहरण (लूप का उपयोग करके)#include <iostream> using namespace std; int main() { int a = 7,

  1. - C++ प्रोग्राम: GCD (महत्तम समापवर्तक) खोजें

    परिचयदो संख्याओं का महत्तम समापवर्तक (GCD) वह सबसे बड़ी संख्या है जो दोनों को विभाजित करती है। उदाहरण के लिए: मान लें हमारे पास दो संख्याएं हैं 45 और 27। 45 = 5 * 3 * 3 27 = 3 * 3 * 3 इसलिए, 45 और 27 का GCD 9 है। उदाहरण 1 (यूक्लिडियन एल्गोरिदम)#include <iostream> using namespace std; int gcd(