自动搬运

查看原文

来自洛谷，原作者为

	在想Peach 这个家伙是个懒狗，但留下了个人介绍的图

搬运于2025-08-24 21:40:34，当前版本为作者最后更新于2019-07-09 14:43:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

C艹里算挺短的代码吧

对于一个类似的东西进行前缀和：

G R G G R G

G：1 1 2 3 3 4

R：0 1 1 1 2 2

差：1 0 1 2 1 2

所得关于差的数列，同样的数最左最右的位置差为一个答案，选取最大的答案即为解，注意为0特判位置即答案。

至于为什么，用前缀和的思想，同位差相等那么这段区间的差就相等，所以记录一个差的最早出现位置就行，注意负数溢出，加上一个常数便可。

code：

#include<iostream>
using namespace std;
string s;
int ans,p[2000005],last=1000000;
int main()
{
	cin>>s;
	for(int i=1;i<=s.length();i++){
		if(s[i-1]=='R')last++;
		else last--;
		if(!p[last])p[last]=i;
		else ans=max(ans,i-p[last]);
		if(last==1000000)ans=i;
	}
	cout<<ans<<endl;
}