illusion7 @ 2020-10-08 17:39:12
f[{g,r}]表示当前有g个G,r个R时的位置。如果当前g==r那么直接更新,否则从同时减去较小的值的状态的位置更新长度。比如第5个R时为f(3,2),同时减去2得到f(1,0),因此长度为f(3,2)-f(1,0)=5-1=4。添加x是为了编号从1开始。因为有时候同时减去一个值会遇到不存在的情况,此时判断为0就不去用这个不存在的状态更新。
#include<bits/stdc++.h>
using namespace std;
string s;
int n,g,r;
map<pair<int,int>,int> f;
int mn,mx;
int main(){
cin>>s;
s="x"+s;
n=s.size();
for(int i=1;i<n;i++){
s[i]=='G' ? g++:r++;
f[make_pair(g,r)]=i;
if(g==r) mx=max(mx,g+r);
else{
mn=min(g,r);
if(f[make_pair(g-mn,r-mn)]!=0)
mx=max(mx,f[make_pair(g,r)]-f[make_pair(g-mn,r-mn)]);
}
}
cout<<mx;
return 0;
}
by illusion7 @ 2020-10-08 17:46:57
输入数据: GGRGGGGGGGGGGRGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGRGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGRGGGGGGGGGGGGGGGGGGGGGGGGRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRGGGGGGGGGGGGGGGGGGGGGGGGGRRRRRRRRRRRRRGGGGGRGRRRRRRRRRRGRRR
输出数据: 126
我的代码输出2