Tìm cách sắp xếp hàng đợi tại thời điểm nhất định trong C ++

Trong bài toán này, chúng ta được cung cấp một chuỗi chỉ bao gồm các ký tự 'M' và 'F' và thời gian t. Nhiệm vụ của chúng tôi là tìm sự sắp xếp của hàng đợi tại một thời điểm nhất định .

Chuỗi xác định những người đứng trong một hàng đợi chung để vào xe buýt. Tất cả nam giới trong hàng đợi đều hào hiệp đến mức nếu họ nhìn thấy một phụ nữ phía sau bất cứ lúc nào, họ sẽ đổi chỗ cho họ. Còn lại t đơn vị thời gian để đi vào xe buýt và mỗi lần trao đổi mất một đơn vị thời gian. Chúng tôi cần tìm các vị trí khi xe buýt đến bằng cách sắp xếp lại hàng đợi.

Hãy lấy một ví dụ để hiểu vấn đề,

Input : queue = "MFMMFF" , t = 3
Output : FFMFMM

Giải thích -

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".

Phương pháp tiếp cận giải pháp

Một cách tiếp cận đơn giản để giải quyết vấn đề là duyệt qua chuỗi đại diện cho hàng đợi T lần. Tìm sự xuất hiện của các cặp "MF" và hoán đổi vị trí của M và F. Và cuối cùng trả về chuỗi cuối cùng.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

The queue after time is over : FFMFMM