题目大意
给定一个循环播放的红绿灯标识字段s，红绿灯一秒变一个颜色，只有三种颜色，红绿黄，现在给出你所在时刻的红绿灯的颜色c，但是你并不知道你所处的具体时间点，求从任意一个颜色是c的点出发后最多经过t秒一定能遇到一个绿灯，求最小的t
题目链接
Problem - 1744C - Codeforces
又是一道我一直卡住的题，不是因为别的，只是不会活学会用罢了，记录这个题就是为了长个教训，尤其是时间超限的情况，一定要想一些更高效的办法。
例如下文中即将用到的lower_bound：
#include<bits/stdc++.h>using namespace std;char s[600000];int main(){int t,k;scanf("%d",&t);while(t--){int n;char c;cin>>n;cin>>c;for(int i=0;i<n;i++){cin>>s[i];s[i+n]=s[i];//重复一遍，方便找到c灯之后的第一个绿灯}if(c=='g'){cout<<0<<endl;}else{vector<int>vec;//用来存绿灯的各位置 for(int i=0;i<2*n;i++){if(s[i]=='g')vec.push_back(i);}int ans=0;for(int i=0;i<n;i++) {if(s[i]==c)//遍历找到c灯位置 {k=lower_bound(vec.begin(),vec.end(),i)-vec.begin();//找到vec中大于等于i的第一个值的位置//也就是c灯后第一个绿灯的位置 ans=max(ans,vec[k]-i);}}cout<<ans<<endl;}} }
