C++ में जोड़ी श्रृंखला की अधिकतम लंबाई

मान लीजिए कि Dota2 की दुनिया में दो पक्ष हैं - द रेडियंट और डायर भी। Dota2 सीनेट में दो पार्टियों से आने वाले सीनेटर होते हैं। अब सीनेट Dota2 गेम में कुछ बदलाव के लिए एक विकल्प बनाना चाहती है। इस परिवर्तन के लिए मतदान एक दौर आधारित प्रक्रिया हो सकती है। प्रत्येक दौर में, प्रत्येक सीनेटर दो अधिकारों में से एक का प्रयोग कर सकता है -

• एक सीनेटर के अधिकार पर प्रतिबंध लगाएं - एक सीनेटर दूसरे सीनेटर को इस दौरान और उसके बाद के सभी दौरों के दौरान अपने सभी अधिकार खो सकता है।

• जीत की घोषणा करें - अगर इस सीनेटर ने पाया कि सीनेटर जिनके पास अभी भी वोट देने का अधिकार है, वे सभी एक समान पार्टी से हैं, तो वह जीत की घोषणा कर सकते हैं और खेल के भीतर बदलाव के बारे में चुनाव कर सकते हैं।

प्रत्येक सीनेटर की पार्टी का प्रतिनिधित्व करने वाली एक स्ट्रिंग को देखते हुए। वर्ण 'आर' और 'डी' क्रमशः रेडियंट पार्टी और डायर पार्टी का प्रतिनिधित्व करते हैं। फिर अगर n सीनेटर हैं, तो दिए गए स्ट्रिंग के आयाम n होंगे।

दिए गए क्रम में प्राथमिक सीनेटर से अंतिम सीनेटर तक राउंड-आधारित प्रक्रिया शुरू होती है। यह प्रक्रिया मतदान के अंत तक चलेगी। प्रक्रिया के दौरान अपने अधिकारों को खोने वाले सभी सीनेटरों को छोड़ दिया जाएगा।

मान लीजिए कि प्रत्येक सीनेटर काफी समझदार है और अपनी पार्टी के लिए सबसे सरल रणनीति खेल सकता है, तो आप भविष्यवाणी करना चाहेंगे कि कौन सी पार्टी अंततः जीत की घोषणा करेगी और Dota2 गेम में बदलाव करेगी। आउटपुट दीप्तिमान या सख्त होना चाहिए।

तो अगर इनपुट "आरडीडी" जैसा है, तो यह सख्त होगा। ऐसा इसलिए है क्योंकि पहला सीनेटर रेडियंट से आता है और वह सिर्फ 1 राउंड में अगले सीनेटर के अधिकार पर प्रतिबंध लगा सकता है। और दूसरा सीनेटर अब किसी भी अधिकार का प्रयोग नहीं कर सकता क्योंकि उसके अधिकार पर प्रतिबंध लगा दिया गया है। उसके बाद तीसरा सीनेटर डायर से आता है और वह राउंड 1 में पहले सीनेटर के अधिकार पर प्रतिबंध लगा सकता है। अब राउंड 2 में, तीसरा सीनेटर सिर्फ जीत की घोषणा कर सकता है क्योंकि सीनेट में केवल वही व्यक्ति है जो वोट दे सकता है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक कतार q1, q2, n :=स्ट्रिंग का आकार बनाएं। सभी R के लिए q1 में, और सभी D के लिए, q2 में डालें।

• जबकि दोनों कतारें खाली नहीं हैं

  • यदि q1 का अगला तत्व

    • n को q1 में डालें, q2 और q1 से हटाएं

  • अन्यथा n को q2 में डालें, q2 और q1 से हटाएं

  • 1 से n बढ़ाएँ

• यदि कतार खाली है, तो सख्त वापसी करें, अन्यथा, दीप्तिमान लौटें

उदाहरण(C++)

आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string predictPartyVictory(string s) {
      queue <int> q1, q2;
      int n = s.size();
      for(int i = 0; i < s.size(); i++){
         if(s[i] == 'R'){
            q1.push(i);
         } else {
            q2.push(i);
         }
      }
      while(q1.size() && q2.size()){
         if(q1.front() < q2.front()){
            q1.push(n);
            q2.pop();
            q1.pop();
         } else {
            q2.push(n);
            q2.pop();
            q1.pop();
         }
         n++;
      }
      return q1.empty()? "Dire" : "Radiant";
   }
};
main(){
   Solution ob;
   cout <<(ob.predictPartyVictory("RDD"));
}

इनपुट

"RDD"

आउटपुट

Dire