[NOIP2008 提高组] 笨小猴
来自洛谷:[https://www.luogu.com.cn/problem/P1125]
Openjudge:[http://noi.openjudge.cn/ch0109/06/]
普及难度，其实不难。
- 我们先审题.
设 maxn 是单词中出现次数最多的字母的出现次数，minn 是单词中出现次数最少的字母的出现次数
第一行输入字符串，假设输入的的单词是 Lucky Word，那么输出 Lucky Word，否则输出 No Answer；
第二行是一个整数，如果输入单词是 Lucky Word，输出 maxn−minn 的值，否则输出 0。
- 我们如何统计出现字母的次数？我这里采用 桶思想 ，我们定义一个整型数组 b ，输入的字符串为 str (string str);
我们可以知道字符都是小写字母，根据ASCII 表最小的小写字母是 97-a 所以我们把 a 作为 0 所以可以表示为 str[i-97] 这样我们就能把26个字母列为 0-25。如果给一个字符串为：abc，我们就可以给他们记四个桶为 0-1-2 。 - 接下来我们要给桶装“水”了 b[str[i]-97]++。我们就可以为桶 0-1-2 都倒上一杯“水”。
| a | b | c |
| ---- | ---- | ---- |
| 1 | 1 | 1 | - 接着就是找出桶中“水”最多 maxn 和最少 minn 了。
- 质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。 在一般领域，对正整数n，如果用2到|根号2|之间的所有整数去除，均无法整除，则n为质数。 依据这些定义我们很容易写出判断质数的代码。
- 我们用桶将 maxn 和 minn 求出之后代入质数判断，若为：输出 Lucky Word endl maxn-minn，反之：输出 No Answer endl 0(输出 0 )。
成品代码：
#include<bits/stdc++.h>
using namespace std;
string s;
int maxn,minn,b[27];
int main(){
//桶
getline(cin,s);
for(int i=0;i<s.size();i++)
b[s[i]-97]++;
for(int i=0;i<26;i++){
if(b[i]==0)
continue;
if(minn==0)
minn=b[i];
maxn=max(maxn,b[i]);
minn=min(minn,b[i]);
}
//质数判断
if(maxn-minn<2){ //小于2的不是质数，排除。
cout<<"No Answer"<<endl<<"0";
return 0;
}
for(int i=2;i*i<=maxn-minn;i++){ //i*i等价于(maxn-minn)的平方
if((maxn-minn)%i==0){
cout<<"No Answer"<<endl<<"0";
return 0;
}
}
cout<<"Lucky Word"<<endl<<maxn-minn;
return 0;
}