P76017 队伍交换 — 题解

专题： 模拟与枚举
适用题目： 新生 OJ 本地题包中的 P76017，不要直接用于外站同名题。

解题思路

模拟每一秒，用从左到右的指针找 BG 并交换；发生交换后指针跳过后一人。

复杂度

时间 $O(nt)$，额外空间 $O(n)$。

易错点

同一秒内不能让同一个人移动两次。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int main(void) {
    int n,t; char s[105]; scanf("%d%d%104s",&n,&t,s);
    for (int second=0;second<t;second++) for(int i=0;i+1<n;i++) {
        if(s[i]=='B' && s[i+1]=='G'){s[i]='G'; s[i+1]='B';i++;}
    }
    puts(s);
    return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,t;
    string s;
    cin>>n>>t>>s;
    while(t--)for(int i=0;i<n-1;i++)if(s[i]=='B'&&s[i+1]=='G'){
        swap(s[i],s[i+1]);
        i++;
    }
    cout<<s<<nl;
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。