Good morning [字符串]

2019-11-06 06:23:58

字体：大中小

来源：转载

供稿：网友

给定一个只有小写字母构成的非空字符串，可以从字符串中任选字符并任意规定顺序，每个字符只能用一次。

最多可以构成多少个”goodmorning”子串(可以重叠)。

比如说：字符串aaavbbbddgggooooooddmmrrnnnnii，可以构成goodmorningoodmorning，共2个。

输入有多组测试数据，请处理到文件结束。

每组数据给定一个只有小写字母构成的非空字符串str。后台所有数据保证1 <= |str| <= 10^5。

输出每组数据输出一个整数，表示最多可以构成的”goodmorning”子串。

样例输入 aaavbbbddgggooooooddmmrrnnnnii goodmorninn goodmorning 样例输出 2 0 1

#include<cstdio>#include<cstring>#include<cmath>#include<stack>#include<queue>#include<algorithm>using namespace std;#define INF 0x3f3f3f3f#define ll long longchar s[100005];int main(){ while (~scanf("%s",s)){ int len = strlen(s); int a[150]; memset(a,0,sizeof(a)); for (int i = 0 ; i < len; ++i){ if (s[i] == 'g') a[s[i]-'a']++; if (s[i] == 'o') a[s[i]-'a']++; if (s[i] == 'm') a[s[i]-'a']++; if (s[i] == 'd') a[s[i]-'a']++; if (s[i] == 'r') a[s[i]-'a']++; if (s[i] == 'n') a[s[i]-'a']++; if (s[i] == 'i') a[s[i]-'a']++; } if (a['g'-'a'] >= 3) a['g'-'a'] += 1; a['g'-'a']/=2; a['o'-'a']/=3; a['n'-'a']/=2; int min = 0x3f3f3f3f; if (min > a['g'-'a']) min = a['g'-'a']; if (min > a['o'-'a']) min = a['o'-'a']; if (min > a['d'-'a']) min = a['d'-'a']; if (min > a['m'-'a']) min = a['m'-'a']; if (min > a['r'-'a']) min = a['r'-'a']; if (min > a['n'-'a']) min = a['n'-'a']; if (min > a['i'-'a']) min = a['i'-'a']; PRintf("%d/n",min); } return 0;}

一道水题 code速度太慢代码而且麻烦续更

上一篇：Haskell语言学习笔记（14）Foldable

下一篇：将一个数组拆分成两个数组，两个数组的差的绝对值最小