[数据结构与算法]笨小猴 计蒜客

题目描述：

笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！

这种方法的具体描述如下：假设 maxn 是单词中出现次数最多的字母的出现次数， minn 是单词中出现次数最少的字母的出现次数，如果 maxn-minn 是一个质数，那么笨小猴就认为这是个 Lucky Word，这样的单词很可能就是正确的答案。

输入格式

只有一行，是一个单词，其中只可能出现小写字母，并且长度小于 100。

输出格式

共两行，第一行是一个字符串，假设输入的的单词是 Lucky Word ，那么输出“Lucky Word”，否则输出“No Answer”；

第二行是一个整数，如果输入单词是 "Lucky Word" ，输出 maxn-minn 的值，否则输出 0 。

样例说明

样例1：

单词 "error" 中出现最多的字母 'r' 出现了 3次，出现次数最少的字母出现了 1 次，3-1=2 ,2 是质数。

样例2：

单词 "olympic" 中出现最多的字母 'i' 出现了 2次，出现次数最少的字母出现了 1次， 2-1=1 ,1 不是质数。

输入? ? ? ? ? ? ? ? ? ? ? ? 输出

error? ? ? ? ? ? ? ? ? ? ??Lucky Word

? ? ? ? ? ?2

olympic? ? ??No Answer

? ? ? ? ? ?0

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
char sh[110];
int str[30];

int sushu(int x) {
?? ?if (x == 0 || x == 1)
?? ??? ?return 0;//0和1不是质数
?? ?for (int i = 2; i * i <= x; i++) {
?? ??? ?if (x % i == 0)
?? ??? ??? ?return 0;
?? ?}
?? ?return 1;
}//质数判断

int main() {
?? ?gets(sh);
?? ?int l = strlen(sh);
?? ?for (int i = 0; i < l; i++) {
?? ??? ?str[sh[i] - 'a']++;
?? ?}//统计a~z各个字母的出现次数
?? ?sort(str, str + 26);//将出现次数按从小到大的顺序排序
?? ?int m = -1;
?? ?for (int i = 0; i < 26; i++) {
?? ??? ?if (str[i] != 0) {
?? ??? ??? ?m = str[i];
?? ??? ??? ?break;
?? ??? ?}
?? ?}//排除出现次数为0的字母，得到字符串中出现次数最少的字母的出现次数
?? ?int t = str[25] - m;//得到最多次数和最少次数的差值
?? ?if (sushu(t))//调用外部函数，判断t是否为质数
?? ??? ?printf("Lucky Word\n%d", t);
?? ?else
?? ??? ?printf("No Answer\n0");
?? ?return 0;
}

如果出现问题，欢迎指正呀