Tìm trạng thái hàng đợi sau thời gian t trong C++

Cho chuỗi ký tự 'M' (nam) và 'F' (nữ) đại diện hàng đợi, và thời gian t. Mỗi đơn vị thời gian, mọi cặp "MF" liền kề sẽ đổi chỗ thành "FM". Nhiệm vụ: tìm trạng thái hàng đợi sau t đơn vị thời gian.

Ví dụ minh họa

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

Phương pháp giải

Mô phỏng t lần: mỗi lần duyệt chuỗi, tìm cặp "MF" và đổi chỗ, bỏ qua ký tự sau khi đã đổi để tránh đổi chồng chéo.

Ví dụ chương trình

#include <iostream> 
using namespace std; 

string rearrangeQueue(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') {
                swap(queue[j], queue[j + 1]);
                j++; // Bỏ qua vị trí vừa đổi
            }
    return queue;
}

int main() {
    int n = 6, t = 3;
    string queue = "MFMMFF";
    cout << "Hàng đợi sau " << t << " thời gian: " << rearrangeQueue(n, t, queue);
    return 0;
}

Kết quả

Hàng đợi sau 3 thời gian: FFMFMM