题目翻译

问当前字符后的第一个 $\tt{g}$ 与它的距离最大是多少。

当前字符可能有很多个。

题目思路

我们把目前找到的当前字符的位置记录下来，找到最早的，记录一下时间差，取个最大。

但显然我们不能对每一个去找，必须几个打包一找。

我用 queue 模拟题意，详情见代码。

由于当前的可能要到下一个循环才能看见 $\tt{g}$，所以要循环两次。

时间复杂度 $\mathcal O(n)$。

题目代码

#include<bits/stdc++.h>
using namespace std;
int t,n,z;
char c[200020];
char tmp;
queue<int>q;
int ans=INT_MIN;
void solve()
{
    ans=INT_MIN;
    while(!q.empty())
    {
        q.pop();
    }
    scanf("%d %c%s",&n,&tmp,c+1);
    for(int i=1;i<=n+n;i++)
    {
        z=i;
        if(z>n)
        {
            z-=n;
        }
        if(i<=n&&c[z]==tmp)
        {
            q.push(z);
        }
        if(c[z]=='g'&&!q.empty())//找到g并且有当前字符
        {
            ans=max(ans,i-q.front());//取一个最大的时间差
            while(!q.empty())
            {
                q.pop();
            }
        }
    }
    printf("%d\n",ans);
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        solve();
    }
    return 0;
}
/*
6
5 r
rggry
1 g
g
3 r
rrg
5 y
yrrgy
7 r
rgrgyrg
9 y
rrrgyyygy
*/