欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客 排数字(简单找规律)

程序员文章站 2022-03-24 14:29:24
...

题目链接:点击这里

牛客 排数字(简单找规律)
牛客 排数字(简单找规律)

1166 以外的不需要考虑。

要让 616616 子串最多一定是 6161661616…,这样后面的串可以用前面的 66 ,数量为min(cnt61, cnt1)min⁡(cnt6−1,\ cnt1)

时间复杂度 O(S)O(∣S∣)

#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<queue>
#include<map>
#include<set>

using namespace std;
typedef long long ll;
const int MOD = 10000007;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int maxn = 200010;
int a[maxn];
int n;
char s[maxn];

int main()
{
	scanf("%d", &n);
	scanf("%s", s);
	
	int cnt1 = 0, cnt6 = 0;
	for(int i = 0; i < n; ++i)
	{
		if(s[i]=='1')    cnt1++;
		else if(s[i]=='6')    cnt6++;
	}
	
	if(cnt1==0||cnt6==0||cnt6==1)
	{
		printf("0\n");
		return 0;
	}
	
	if(cnt1<cnt6)	printf("%d\n", cnt1);
	else if(cnt1==cnt6)	printf("%d\n", cnt6-1);
	else if(cnt6<cnt1)	printf("%d\n", cnt6-1);
	
	return 0;
}
相关标签: 思维