90分!WA了第二个点
  • 板块P2697 宝石串
  • 楼主oh_my_shy
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/7/12 08:08
  • 上次更新2023/11/4 15:03:11
查看原帖
90分!WA了第二个点
416442
oh_my_shy楼主2021/7/12 08:08
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char c[1000005];
int n,a[1000005],sum[1000005],ans=-0x7fffffff;
int main(){
	cin>>c;
	n=strlen(c);
	for(int i=1;i<=n;i++){
		if(c[i-1]=='G')a[i]=-1;
		if(c[i-1]=='R')a[i]=1;
	}
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(((i-j)%2)&&sum[i]-sum[j-1]==0){
				ans=max(i-j+1,ans);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

方法: 绿色当成-1,红色当成1

求前缀和

然后再枚举i和j

如果符合条件就更新答案

2021/7/12 08:08
加载中...