Codeforces Round #828 (Div. 3)C. Traffic Light_c. traffic light codeforces

题外：这题居然没过掉，当时第一想法就是暴力，被t掉后，换了种写法，但是出了点小问题，那就写写这道简单题的题解吧，以此深省。

题意：给一个字符串s和字符c,s由'r','y','g',分别代表红黄绿交通灯，s即为所给交通信号灯的循环信息，每一秒换一下，当为绿灯时可通过。当前亮灯由字符c给出，但不知当前时间，即不知是s里的哪个状态。找到保证能过马路的最短等待时间。

题解：贪心即可，既然要保证能通过，对于所有c肯定要找到'g'-'c' 位置最大的那个。但要求等待时间最短，即对于每一个c找到离他最近的那个'g‘即可。若当前为'g'就直接输出0即可。

对于一个c往后找若没有'g'那个只能是下一次循环的第一个’g'.

怎么是实现呢，读入字符时，把所有c和’g'的位置记录一下，然后遍历c的所有位置，对于每一个位置，去‘g'位置里找离他最近的即可，查找可用二分，然后求一下最大值。

代码：

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n;
    char c;
    cin>>n>>c;
    string s;
    cin>>s;
    vector<int>a;
    vector<int>b;
    for(int i=0;i<s.size();i++)//记录位置
    {
        if(s[i]==c)a.push_back(i);
        if(s[i]=='g') b.push_back(i);
    }
    if(c=='g') //当前若为'g'直接通过，不用等
    {
    	cout<<"0\n";return;
	}
    int res=0;
    for(auto t:a)//遍历c的位置
    {
       int x =upper_bound(b.begin(),b.end(),t)-b.begin();//二分
       if(x==b.size()) x = n-t+b[0];//特殊情况，即c后边没'g'时，就把第一个'g'给他
       else x=b[x]-t;
       res=max(res,x);
    }
    cout<<res<<"\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
 
 
    return 0;
}