ในปัญหานี้ เราได้รับสตริงที่ประกอบด้วยอักขระ 'M' และ 'F' เท่านั้น และเวลา t งานของเราคือ ค้นหาการจัดคิวในเวลาที่กำหนด .
สตริงกำหนดคนที่ยืนอยู่ในคิวทั่วไปเพื่อเข้าสู่รถบัส ผู้ชายทุกคนในคิวกล้าหาญมากจนหากพวกเขาเห็นผู้หญิงข้างหลังพวกเขา ณ จุดใดเวลาหนึ่ง พวกเขาจะแลกเปลี่ยนสถานที่กับพวกเขา เหลือเวลาอีกหน่วยในการขึ้นรถบัสและการแลกเปลี่ยนแต่ละครั้งจะใช้เวลาหนึ่งหน่วยเวลา เราต้องหาตำแหน่งเมื่อรถมาโดยจัดคิวใหม่
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input : queue = "MFMMFF" , t = 3 Output : FFMFMM
คำอธิบาย −
In T = 0 -> 1, 'M' at position 1 changes position with 'W' at 2 and 'M' at position 4 changes position with 'W' at 5. Queue becomes - "FMMFMF". In T = 0 -> 1, 'M' at position 3 changes position with 'W' at 4 and 'M' at position 5 changes position with 'W' at 6. Queue becomes - "FMFMFM". In T = 0 -> 1, 'M' at position 2 changes position with 'W' at 3 and 'M' at position 4 changes position with 'W' at 5. Queue becomes - "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<<"The queue after time is over : "<<rearrageQueue(n, t, queue);
return 0;
} ผลลัพธ์
The queue after time is over : FFMFMM
