AT5158 [AGC037A] Dividing a String 题解

😇description

• 给定一个字符串 $S$，请你找出一个最大的 $k$，使得将这个字符串划分成 $k$ 段后能够保证相邻的两段不相同。

• $1\le |S| \le 2\times 10^5$，且保证 $S$ 串内均为小写字母。

• translate by @ShineEternal。

solution

我们贪心的进行划分，每次遇到一个和上一次不一样的串就可以单独提取出来一次了。

code

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
char s[200005];
int main()
{
	int cnt=0;
	scanf("%s",&s);
	int n=strlen(s);
	string a="",b="";
	for(int i=0;i<n;i++)
	{
		a+=s[i];
		if(a!=b)
		{
			b=a;
			cnt++;
			a="";
		}
	}
	printf("%d\n",cnt);
	return 0;
}