Codeforces 266B Queue at the School 學校的排隊

難易度 : 800

英文原文如下

During the break the schoolchildren, boys and girls, formed a queue of n people in the canteen. Initially the children stood in the order they entered the canteen. However, after a while the boys started feeling awkward for standing in front of the girls in the queue and they started letting the girls move forward each second.

Let’s describe the process more precisely. Let’s say that the positions in the queue are sequentially numbered by integers from 1 to n, at that the person in the position number 1 is served first. Then, if at time x a boy stands on the i-th position and a girl stands on the (i + 1)-th position, then at time x + 1 the i-th position will have a girl and the (i + 1)-th position will have a boy. The time is given in seconds.

You’ve got the initial position of the children, at the initial moment of time. Determine the way the queue is going to look after t seconds.

中文翻譯

在學校的用餐休息時間，男孩加上女孩共 n 個人在食堂排著隊。最初，學生們站在他們本來的位置上。但是，經過一下之後，男孩們開始對站在女孩們面前覺得尷尬，所以他們每一秒開始讓女孩們往前移動。

讓我們更精確點地形容整個過程，假設隊伍本來的編號是從 1 到 n，然後號碼 1 的人最早被服務。

然後，如果在時間 x，一個男孩站在第 i 個位置，而一個女孩站在(i+1)位置，那麼在時間 x+1，第 i 個位置將有一個女孩，而(i+1)位置將有一個男孩。時間以秒為單位。

你已經得到了孩子們在初始時間的初始位置。確定在 t 秒後隊列的樣子。

輸入

The first line contains two integers n and t (1 ≤ n, t ≤ 50), which represent the number of children in the queue and the time after which the queue will transform into the arrangement you need to find.

The next line contains string s, which represents the schoolchildren’s initial arrangement. If the i-th position in the queue contains a boy, then the i-th character of string s equals “B”, otherwise the i-th character equals “G”.

第一行包含了兩個字串 n 以及 t (1 ≤ n, t ≤ 50)，分別代表了排隊的孩子數量以及隊伍會經過多少秒。

下一行包含了字串 s，代表的則是隊伍最開始的順序。要是第 i 位是男生，那第i個字元就是 “B”，不然的話就是 “G” (女生)。

輸出

Print string a, which describes the arrangement after t seconds. If the i-th position has a boy after the needed time, then the i-th character a must equal “B”, otherwise it must equal “G”.

印出字串 a，描述了 t 秒後順序。如果 t 秒後第 i 位是男生，那第i個字元就是 “B”，不然的話就是 “G” (女生)。

範例

解題思路

我們可以用一個 for 迴圈來模擬時間的流逝，然後用一個 while 來模擬隊伍的移動。

C#解決方案

方案1

string[] arr = Console.ReadLine().Split(" ");
int n = int.Parse(arr[0]);
int t = int.Parse(arr[1]);

char[] s = Console.ReadLine().ToCharArray();

for (int time = 0; time < t; time++)
{
    int i = 0;
    while (i < n - 1)
    {
        if (s[i] == 'B' && s[i + 1] == 'G')
        {
            char tmp = s[i];
            s[i] = s[i + 1];
            s[i + 1] = tmp;

            i += 2;
        }
        else
        {
            i += 1;
        }
    }
}

Console.WriteLine(new string(s));

while 逐一判斷有沒有女孩在男孩身後，要是有則將兩人位置互換。

結論

紳士精神，永不過時~

但解決這題卻沒有想像中來的簡單，花了一點時間想整個流程呢~

這一題出自比賽 – Dashboard – Codeforces Round 163 (Div. 2) – Codeforces

然後這裡看這一系列的其他題目

• Codeforces 266A Stones on the Table 桌上的石頭

🧡如果文章有幫上你的忙，那是我的榮幸

🧡分享文章或是留一個言，那都是對我的支持

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Problem – 266B – Codeforces

一些其他的Codeforces文章