JZTXT

Luogu P2697 宝石串

发布时间 2023-05-24 18:35:41作者: Gery_8002

题目

link

思路

将字符串中 \(G\) 换为 \(-1\), \(R\) 换为 \(1\), 进行前缀和处理, 若和为 \(0\), 则为稳定的宝石串，比较记录最大值

Code

#include <bits/stdc++.h>

using namespace std;

string s;
int l[1000005], k[1000005], maxn = 0;

int main() {
	getline(cin, s);
	int len = s.length();
	for (int i = 0; i < len; i++) {
		if (s[i] == 'R') l[i] = -1;
		else if (s[i] == 'G') l[i] = 1;
	}
	k[0] = l[0];
	for (int i = 1; i < len; i++)
		k[i] = k[i-1] + l[i];
	for (int i = 0; i < len; i++)
		for (int j = i; j < len; j++)
			if (k[j] - k[i-1] == 0)
				maxn = max(maxn, j - i + 1);
			
	printf("%d", maxn);
	return 0;
}