इस समस्या में, हमें केवल 'M' और 'F' वर्णों से युक्त एक स्ट्रिंग और एक समय t दिया गया है। हमारा कार्य दिए गए समय पर कतार की व्यवस्था ज्ञात करना है।
स्ट्रिंग बस में प्रवेश करने के लिए एक सामान्य कतार में खड़े लोगों को परिभाषित करती है। कतार में सभी पुरुष इतने शिष्ट हैं कि यदि वे किसी भी समय अपने पीछे एक महिला देखते हैं तो वे उनके साथ स्थान बदल लेते हैं। बस आने में t इकाई समय शेष है और प्रत्येक विनिमय में एक इकाई समय लगता है। हमें कतार को पुनर्व्यवस्थित करके बस आने पर स्थितियों को ढूंढना होगा।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट : कतार = "MFMMFF" , t = 3 आउटपुट : FFMFMM
व्याख्या −
T = 0 -> 1 में, स्थिति 1 पर 'M' स्थिति 2 पर 'W' के साथ स्थान बदलता है और स्थिति 4 पर 'M' स्थिति 5 पर 'W' के साथ स्थान बदलता है। कतार बन जाती है - "FMMFMF"। T = 0 -> 1 में, स्थिति 3 पर 'M' स्थिति 4 पर 'W' के साथ स्थान बदलता है और स्थिति 5 पर 'M' स्थिति 6 पर 'W' के साथ स्थान बदलता है। कतार बन जाती है - "FMFMFM"। T = 0 -> 1 में, स्थिति 2 पर 'M' स्थिति 3 पर 'W' के साथ स्थान बदलता है और स्थिति 4 पर 'M' स्थिति 5 पर 'W' के साथ स्थान बदलता है। कतार बन जाती है - "FFMFMM"।
समाधान दृष्टिकोण
समस्या को हल करने का एक सरल दृष्टिकोण कतार को दर्शाने वाली स्ट्रिंग को T बार पार करना है। "MF" जोड़े की घटना ढूंढें और M और F की स्थितियों को स्वैप करें। और अंत में अंतिम स्ट्रिंग लौटाएं।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम
#include <iostream> using namespace std; string rearrageQueue(int n, int t, string queue) { for (int i = 0; i < t; i++) for (int j = 0; j < n - 1; j++) if (queue[j] == 'M' && queue[j + 1] == 'F') { queue[j] = 'F'; queue[j + 1] = 'M'; j++; } return queue; } int main() { int n = 6, t = 3; string queue = "MFMMFF"; cout<<"समय समाप्त होने के बाद कतार : "<<rearrageQueue(n, t, queue); return 0; } आउटपुट
समय समाप्त होने के बाद कतार : FFMFMM