算法竞赛--子串是连续的(规律)

子串是连续的

小明最喜欢的字符串是616.

他得到了一个纯数字的字符串S,他想知道在可以任意打乱S顺序的情况下，最多有多少个怒同的子串为616.

当两个子串S[l1…r1],S[l2…r2]满足l1不等于l2或r1不等于r2时认为它们是不同的

输入描述:

第一行，一个正整数s,表示s的长度

第二行，一个字符串s,其字符集为{0,1,2,3,4,5,6,7,8,9}。

保证1<=|s|<=200000。

输出描述:

输出一行，一个整数表示答案。

样例输入：

11
11451419266

样例输出:

1

说明

一种最优打乱方案为”11451492616”，有一个子串为”616”。

个人理解:

最初理解为组合数,例如11116666，有四个1,6有六种组合，答案有4种，实际为排序之后为616 16 16 1 三种组合，则说明第一组有两个6，一个1,之后每一组一个1一个6.

代码:

#include <stdio.h>
int main()
{
	int n,c1=0,c6=0,count,sum=0;
	char c;
	scanf("%d",&n);
	getchar();
	for(int i=0;i<n;i++)	//分别记录6和1的个数
	{
		scanf("%c",&c);
		if(c=='6')
			c6++;      
		if(c=='1')
			c1++;
	}
	c6=c6-1;			//减去一个6之后，相当于每组为1和6两个数
	count=c1>=c6?c6:c1; //对1和6的个数进行判断,小的即为所求
	printf("%d",count);
	return 0;
}